Chapter
Theory
A sequence in olympiad algebra is not just a list of numbers. One must understand the rule of change: differences, ratios, recurrence, invariant, or a hidden telescoping sum.
For an arithmetic progression, \(a_n=a_1+(n-1)d\), \(S_n=\frac{n(a_1+a_n)}2\). For a geometric progression, \(a_n=a_1q^{n-1}\), \(S_n=a_1\frac{q^n-1}{q-1}\) for \(q\ne1\). Recurrences are often solved by substitution or induction.
Look for sequences when there is a repeated process, a transition from \(n\) to \(n+1\), a sum of many similar fractions, a maximum number after steps, or a condition “for every \(n\)”.
If neighbouring terms differ by a constant, it is arithmetic. If the ratio is constant, it is geometric. If the expression has the form \(u_k-u_{k+1}\), the sum telescopes. If a process preserves a quantity, look for an invariant.
Do not confuse the index with the term. Do not forget the base case in induction. In recurrences with fractions, check the domain. In sequence-counting problems, first decide what can be chosen freely.
Write the first terms. Inspect differences and ratios. Try a substitution such as \(b_n=a_n+c\) or \(b_n=\frac1{a_n}\). Check telescoping. Formulate the induction step.
Examples
We start with the explicit formula.
Problem. In an arithmetic progression \(a_1=5\), \(d=3\). Find \(a_{20}\).
\(a_{20}=a_1+19d=5+57=62\).
Comment. Do not replace \(19\) by \(20\).
The sums of opposite pairs are constant.
Problem. Find \(7+10+13+\cdots+70\).
This is an arithmetic progression with \(a_1=7\), \(d=3\), \(a_n=70\). From \(7+3(n-1)=70\), \(n=22\). The sum is \(\frac{22(7+70)}2=847\).
Comment. First find the number of terms.
A constant ratio gives a power.
Problem. In a geometric progression \(b_1=3\), \(q=2\). Find \(b_8\).
\(b_8=3\cdot2^7=384\).
Comment. Index \(8\) gives exponent \(7\).
Sometimes the formula is guessed from the first terms and proved by induction.
Problem. The sequence is defined by \(a_1=1\), \(a_{n+1}=a_n+2n+1\). Prove that \(a_n=n^2\).
Base case: \(a_1=1=1^2\). If \(a_n=n^2\), then \(a_{n+1}=n^2+2n+1=(n+1)^2\). Thus the formula holds for all \(n\).
Comment. The difference of consecutive squares is \(2n+1\).
A shift often turns a recurrence into a geometric one.
Problem. Let \(a_1=1\), \(a_{n+1}=2a_n+1\). Find \(a_n\).
Add \(1\): \(a_{n+1}+1=2(a_n+1)\). Hence \(a_n+1=2^n\), so \(a_n=2^n-1\).
Comment. The right substitution removes the constant term.
The sum opens after decomposing the fraction.
Problem. Find \(\sum_{k=1}^{n}\frac1{k(k+1)}\).
\(\frac1{k(k+1)}=\frac1k-\frac1{k+1}\). Therefore the sum is \(1-\frac1{n+1}=\frac n{n+1}\).
Comment. Almost all terms cancel.
A process may preserve not a term, but a combination of terms.
Problem. The sequence is defined by \(a_{n+1}=3a_n+2\), \(a_1=0\). Prove that \(a_n+1\) is a power of \(3\).
\(a_{n+1}+1=3a_n+3=3(a_n+1)\). Since \(a_1+1=1\), we get \(a_n+1=3^{n-1}\).
Comment. The invariant form is \(a_n+1\).
Sometimes a sequence is determined by its start and its steps.
Problem. How many positive integer sequences \(a_1,\ldots,a_5\) have \(a_1=3\) and \(|a_{i+1}-a_i|\le1\)?
Each step is \(-1,0\), or \(1\), but we must ensure that no term becomes zero. Starting from \(3\), in four steps with decrease at most \(1\), reaching zero is impossible. Hence all \(3^4=81\) step choices work.
Comment. The difference sequence is the main object.
Problems
In an arithmetic progression \(a_1=4\), \(d=5\). Find \(a_{15}\).
Use \(a_n=a_1+(n-1)d\).
\(a_{15}=4+14\cdot5=74\).
In a geometric progression \(b_1=2\), \(q=3\). Find \(b_6\).
Use \(b_n=b_1q^{n-1}\).
\(b_6=2\cdot3^5=486\).
Find \(\frac1{1\cdot2}+\frac1{2\cdot3}+\cdots+\frac1{10\cdot11}\).
Decompose \(\frac1{k(k+1)}\).
\(\frac1{k(k+1)}=\frac1k-\frac1{k+1}\). The sum is \(1-\frac1{11}=\frac{10}{11}\).
The sequence is defined by \(a_1=1\), \(a_{n+1}=a_n+2n+1\). Find \(a_{20}\).
Prove that \(a_n=n^2\).
By induction, \(a_n=n^2\). Hence \(a_{20}=400\).
Find the sum of all positive terms of \(53,48,43,\ldots\).
First find the last positive term.
The general term is \(a_n=53-5(n-1)\). Positivity gives \(58-5n>0\), so \(n\le11\). The last term is \(a_{11}=3\).
The sum is \(\frac{11(53+3)}2=308\).
Let \(a_1=2\), \(a_{n+1}=3a_n+4\). Find \(a_n\).
Choose \(c\) so that \(a_{n+1}+c=3(a_n+c)\).
We need \(3c=4+c\), so \(c=2\). Then \(a_{n+1}+2=3(a_n+2)\).
\(a_1+2=4\), hence \(a_n+2=4\cdot3^{n-1}\), and \(a_n=4\cdot3^{n-1}-2\).
Let \(F_1=F_2=1\), \(F_{n+2}=F_{n+1}+F_n\). Prove that \(F_{n+3}\ge2F_n\).
Express \(F_{n+3}\) through \(F_{n+1}\) and \(F_n\).
\(F_{n+3}=F_{n+2}+F_{n+1}=F_n+2F_{n+1}\). Since \(F_{n+1}\ge F_n\) for \(n\ge1\), \(F_{n+3}\ge3F_n\), hence \(F_{n+3}\ge2F_n\).
The sequence \(a_n\) begins \(2,5,10,17,26\). Suppose the second differences are constant. Find a formula for \(a_n\).
First differences are \(3,5,7,9\).
The differences are \(2n+1\) from \(a_n\) to \(a_{n+1}\). This corresponds to \(a_n=n^2+1\). Check: \(1^2+1=2\), \(2^2+1=5\), and so on.
Find \(\sum_{k=1}^{n}\frac{1}{(k+1)(k+3)}\).
Decompose the fraction as \(\frac12\left(\frac1{k+1}-\frac1{k+3}\right)\).
\(\frac{1}{(k+1)(k+3)}=\frac12\left(\frac1{k+1}-\frac1{k+3}\right)\).
The sum is \(\frac12\left(\frac12+\frac13-\frac1{n+2}-\frac1{n+3}\right)\).
Let \(1
Set \(A=\sqrt[2^{n+1}]{a}\), \(B=\sqrt[2^{n+1}]{b}\).
Then \(B>A>1\), \(x_{n+1}=2^{n+1}(B-A)\), and \(x_n=2^n(B^2-A^2)=2^{n+1}(B-A)\frac{A+B}{2}\).
Since \(\frac{A+B}{2}>1\), we get \(x_n>x_{n+1}\).
The sequence is defined by \(a_1=4\), \(a_{n+1}=5a_n+4\). Prove that \(a_n\) is divisible by \(4\) for all \(n\).
Use induction.
Base case is clear: \(4\mid a_1\). If \(4\mid a_n\), then \(5a_n+4\) is also divisible by \(4\). Hence \(4\mid a_{n+1}\).
Let \(a_1=2\), \(a_{n+1}=\frac{2a_n}{a_n+2}\). Find \(\frac1{a_n}\).
Pass to reciprocals.
\(\frac1{a_{n+1}}=\frac{a_n+2}{2a_n}=\frac12+\frac1{a_n}\). Thus \(\frac1{a_n}=\frac12+\frac{n-1}{2}=\frac n2\). Hence \(a_n=\frac2n\).
How many positive integer sequences \(a_1,\ldots,a_n\) have minimum term at most \(4\) and \(|a_{i+1}-a_i|\le1\)?
Fix the differences and the minimum term.
The difference sequence has \(n-1\) terms, each equal to \(-1,0,1\), giving \(3^{n-1}\) choices.
For each difference sequence, all original sequences are obtained by adding the same constant to all terms. Exactly one has minimum \(1,2,3,4\). Therefore the answer is \(4\cdot3^{n-1}\).
For Fibonacci numbers \(F_1=F_2=1\), prove \(F_{n+1}F_{n-1}-F_n^2=(-1)^n\) for \(n\ge2\).
Check the base case and use \(F_{n+2}=F_{n+1}+F_n\) for the step.
Base \(n=2\): \(F_3F_1-F_2^2=2\cdot1-1=1=(-1)^2\).
If \(F_{n+1}F_{n-1}-F_n^2=(-1)^n\), then \(F_{n+2}F_n-F_{n+1}^2=(F_{n+1}+F_n)F_n-F_{n+1}^2=-(F_{n+1}F_{n-1}-F_n^2)=(-1)^{n+1}\).
Let \(0
Consider \(1-a_{n+1}\).
\(1-a_{n+1}=1-2a_n+a_n^2=(1-a_n)^2\). If \(0 Also \(a_{n+1}-a_n=a_n(1-a_n)>0\). Therefore the sequence is increasing.
Prove that \(\sum_{k=1}^{n}\frac1{k^2}<2\) for all \(n\).
For \(k\ge2\), compare \(\frac1{k^2}\) with \(\frac1{k-1}-\frac1k\).
For \(k\ge2\), \(k^2>k(k-1)\), so \(\frac1{k^2}<\frac1{k(k-1)}=\frac1{k-1}-\frac1k\).
Thus the sum is less than \(1+\sum_{k=2}^{n}\left(\frac1{k-1}-\frac1k\right)=1+1-\frac1n<2\).
The sequence is defined by \(a_1=1\), \(a_{n+1}=a_n^2+a_n\). Prove that \(a_n\) is divisible by \(a_1a_2\cdots a_{n-1}\) for \(n\ge2\).
Notice that \(a_{n+1}=a_n(a_n+1)\).
We prove the stronger statement that \(a_n\) is divisible by the product of all previous terms. The base is clear.
If \(a_n\) is divisible by \(a_1\cdots a_{n-1}\), then \(a_{n+1}=a_n(a_n+1)\) is divisible by \(a_1\cdots a_{n-1}\cdot a_n\). Hence the claim follows by induction.
The sequence \(a_n\) has constant second difference \(6\), with \(a_1=2\), \(a_2=9\). Find \(a_n\).
If the second difference is \(6\), the leading coefficient of the quadratic formula is \(3\).
Let \(a_n=3n^2+bn+c\). From \(a_1=2\): \(3+b+c=2\). From \(a_2=9\): \(12+2b+c=9\).
Subtracting gives \(9+b=7\), so \(b=-2\). Then \(c=1\). Answer: \(a_n=3n^2-2n+1\).
In a convex \(n\)-gon, diagonals are drawn one by one so that each new diagonal intersects at most one previously drawn diagonal inside the polygon. Prove that at most \(2n-6\) diagonals can be drawn, and give a construction attaining this number.
For the upper bound, consider the last diagonal and cut the polygon into two parts.
Construction: draw \(A_2A_4,A_3A_5,\ldots,A_{n-2}A_n\), then \(A_1A_3,A_1A_4,\ldots,A_1A_{n-1}\). There are \((n-3)+(n-3)=2n-6\) diagonals, and the order can be chosen so that each new one intersects at most one old one.
For the upper bound, use induction on \(n\). The triangle is clear. Let the last diagonal be \(A_1A_k\). It intersects at most one previous diagonal \(d\). All other diagonals lie inside one of the two polygons \(A_1A_2\ldots A_k\) or \(A_kA_{k+1}\ldots A_nA_1\). By induction, their number is at most \((2k-6)+(2(n+2-k)-6)=2n-8\). Adding the last diagonal and possibly \(d\), we get at most \(2n-6\).
Find all real \(t\) such that \(t\,n(n+3)(n+6)\) is an integer for every positive integer \(n\).
Substitute several small \(n\) to restrict \(t\).
For \(n=1\), \(28t\in\mathbb Z\); for \(n=2\), \(80t\in\mathbb Z\); for \(n=3\), \(162t\in\mathbb Z\). The greatest common divisor of \(28,80,162\) is \(2\), so \(2t\in\mathbb Z\).
Conversely, \(n(n+3)(n+6)\) is always even: if \(n\) is even this is clear, and if \(n\) is odd then \(n+3\) is even. Thus every \(t=\frac{k}{2}\), \(k\in\mathbb Z\), works. Answer: \(t=\frac{k}{2}\).
Call a number rectangular if it equals \(m(m+1)\). Prove that every rectangular number can be represented as a quotient of two rectangular numbers.
Try multiplying \(n(n+1)\) by \(\frac{(n+1)(n+2)}{(n+1)(n+2)}\).
Let the given number be \(n(n+1)\). Then
\[n(n+1)=\frac{n(n+2)(n+1)^2}{(n+1)(n+2)}=\frac{(n^2+2n)(n^2+2n+1)}{(n+1)(n+2)}.\]
The numerator is the product of consecutive integers \(n^2+2n\) and \(n^2+2n+1\), and the denominator \((n+1)(n+2)\) is also rectangular. Thus the representation is found.
Let \(a
Combine suitable multiples of the two vectors to obtain \((D,0)\) and \((0,D)\).
Let \(u=(a,b-a)\), \(v=(b-a,-a)\). Then \(a u+(b-a)v=(a^2+(b-a)^2,0)=(D,0)\).
Also \((b-a)u-a v=(0,D)\). Thus the marking is periodic under shifts \((D,0)\) and \((0,D)\).
In a fundamental \(D\times D\) square, the number of marked cells equals the area of the square divided by the area of the fundamental parallelogram of the lattice. The determinant of \(u,v\) is \(-a^2-(b-a)^2=-D\), so that area is \(D\). Hence a square of area \(D^2\) contains exactly \(D\) marked cells.
How many positive integer sequences \(a_1,\ldots,a_n\) contain at least one term equal to \(4\) or \(5\), and any two neighbouring terms differ by at most \(2\)?
First count sequences with minimum term at most \(5\), then subtract the extra ones.
Fix the differences \(b_i=a_{i+1}-a_i\). Each difference can be \(-2,-1,0,1,2\), giving \(5^{n-1}\) choices.
For each difference sequence, exactly one original sequence has minimum \(1,2,3,4,5\). Thus there are \(5^n\) sequences with minimum at most \(5\).
The extra ones are those with no \(4\) or \(5\). If such a sequence has minimum at most \(5\), step size at most \(2\), and contains a value greater than \(5\) and a value less than \(4\), it must pass through \(4\) or \(5\). Hence the extra sequences consist only of \(1,2,3\). There are \(3^n\) of them. Answer: \(5^n-3^n\).
Let \(1
Set \(A=\sqrt[3^{n+1}]{a}\), \(B=\sqrt[3^{n+1}]{b}\), and factor \(B^3-A^3\).
Then \(B>A>1\), \(y_{n+1}=3^{n+1}(B-A)\), and \(y_n=3^n(B^3-A^3)=3^{n+1}(B-A)\frac{B^2+AB+A^2}{3}\).
Since \(A,B>1\), the average \(\frac{B^2+AB+A^2}{3}>1\). Therefore \(y_n>y_{n+1}\).
Six consecutive positive integers are given. Prove that they can be labelled \(a,b,c,d,e,f\) so that \(\frac a{b+c}+\frac d{e+f}=1\).
Write the numbers as \(n,n+1,\ldots,n+5\) and make equal denominators.
Take \(a=n\), \(d=n+5\), \(b=n+1\), \(c=n+4\), \(e=n+2\), \(f=n+3\).
Then \(b+c=e+f=2n+5\), and \(a+d=2n+5\). Hence \(\frac a{b+c}+\frac d{e+f}=\frac{a+d}{2n+5}=1\).
Eight consecutive positive integers are given. Prove that six of them can be labelled \(a,b,c,d,e,f\) so that \(\frac a{b+c}+\frac d{e+f}=1\).
Take the first six numbers and apply the symmetric construction.
Among the given numbers are \(n,n+1,\ldots,n+7\). Take the first six: \(n,\ldots,n+5\).
As in the previous construction, set \(a=n\), \(d=n+5\), \(b=n+1\), \(c=n+4\), \(e=n+2\), \(f=n+3\). Then both denominators equal \(2n+5\), and \(a+d=2n+5\). Hence the sum is \(1\).
Ladders