Star problems Advanced ← Back to chapter

Sequences and Series: Star problems

Ten optional challenges to stretch your reasoning. Work on paper, use hints when you need them, and check the answer or full solution when you are ready. You can skip these problems and continue the course.

1 of 3 stars: Stretch
2 of 3 stars: Challenge
3 of 3 stars: Deep challenge

Stars indicate difficulty within this set.

0 of 10 completed

Progress saved in this browser.

Problem 1 of 10

Problem 1 Two starting values

Difficulty: 1 of 3 stars, Stretch

A sequence satisfies $a_1=2$ , $a_2=t$ , and $a_{n+2}=a_n+6$ for every positive integer $n$ . Find all real $t$ for which every term is a positive integer and the entire sequence is strictly increasing.

Among those possibilities, the first $100$ terms sum to $15050$ . Find $t$ , and determine whether this extra information forces the entire sequence to be arithmetic.
1. Hint 1
  Treat the odd-indexed and even-indexed terms separately.
2. Hint 2
  The gaps between consecutive terms alternate between two values. For the sum, pair $a_{2k-1}$ with $a_{2k}$ .
Answer

The admissible values are $t=3,4,5,6,7$ . The stated sum forces $t=5$ , giving $a_n=3n-1$ , an arithmetic sequence.

Full solution

The recurrence gives $a_{2k-1}=2+6(k-1)$ and $a_{2k}=t+6(k-1)$ for every $k\ge1$ .
All terms are integers exactly when $t$ is an integer.
Strict increase requires the alternating gaps $a_{2k}-a_{2k-1}=t-2$ and $a_{2k+1}-a_{2k}=8-t$ to be positive.
Thus $2<t<8$ , giving the five reported integer values; positivity then follows from $a_1=2$ and strict increase.

For $k=1,\ldots,50$ , a pair sums to
$a_{2k-1}+a_{2k}=t+2+12(k-1).$
Therefore the first $100$ terms sum to
$50(t+2)+12(0+1+\cdots+49)=14800+50t.$
Equating this to $15050$ gives $t=5$ .
Both alternating gaps are then $3$ , so the full sequence is arithmetic, with
$a_n=2+3(n-1)=3n-1.$
For the other admissible values, the two gaps differ; two interleaved arithmetic subsequences need not themselves form one arithmetic sequence.

Answer

The admissible values are $t=3,4,5,6,7$ . The stated sum forces $t=5$ , giving $a_n=3n-1$ , an arithmetic sequence.

Key idea

A recurrence that skips an index may describe interleaved sequences with different local behavior.
Problem 1: Mark complete
Problem 2 Four integer terms

Difficulty: 1 of 3 stars, Stretch

Find every ordered four-term geometric sequence of positive integers whose sum is $130$ . The common ratio is not assumed to be an integer. Prove that your list is complete.
1. Hint 1
  If the ratio in lowest terms is $p/q$ , integrality of all four terms forces them to be $tq^3,tpq^2,tp^2q,tp^3$ for a positive integer $t$ .
2. Hint 2
  Factor the sum as $t(p+q)(p^2+q^2)$ . The inequality $p^2+q^2\ge(p+q)^2/2$ gives a small bound on $p+q$ .
Answer

The sequences are $(16,24,36,54)$ and $(54,36,24,16)$ .

Full solution

Reversing a sequence replaces its ratio by its reciprocal, so first consider ratios $p/q\ge1$ in lowest positive integer terms.
If the first term is $a$ , the fourth is $ap^3/q^3$ .
Since $p^3,q^3$ are relatively prime, integrality forces $q^3$ to divide $a$ .
Thus the terms have the form $tq^3,tpq^2,tp^2q,tp^3$ with positive integer $t$ , and their sum is
$t(p+q)(p^2+q^2)=130.$

Write $s=p+q\ge2$ .
From $(p-q)^2\ge0$ we get $p^2+q^2\ge s^2/2$ , hence
$s^3/2\le130.$
In particular $s\le6$ , since $7^3>260$ .
Also $s$ divides $130$ , so only $s=2$ or $s=5$ remain.
For $s=2$ , $p=q=1$ gives sum $4t$ , which cannot equal $130$ .
For $s=5$ with $p\ge q$ , the pairs are $(4,1)$ and $(3,2)$ .
They give sums $85t$ and $65t$ , respectively.
Only the second works, with $t=2$ .

This yields $(16,24,36,54)$ with ratio $3/2$ .
Reversing gives the other listed sequence, with ratio $2/3$ .
Both sum to $130$ , and the bound on $s$ proves that no unexamined ratios remain.

Answer

The sequences are $(16,24,36,54)$ and $(54,36,24,16)$ .

Key idea

Integer terms can have a noninteger geometric ratio; put that ratio in lowest terms before using divisibility.
Problem 2: Mark complete
Problem 3 A missing exponent

Difficulty: 1 of 3 stars, Stretch

In the expansion of $(1+ax)^n$ , the integer $n\ge3$ and the real number $a>0$ are unknown. The coefficient of $x$ is $15/4$ , and the coefficients of $x^2$ and $x^3$ are equal.

Find $n,a$ . Then prove exactly which coefficients in the expansion are largest, without listing all of them.
1. Hint 1
  Use the Binomial Theorem to write the first three coefficients in terms of $n$ and $a$ .
2. Hint 2
  For the largest-coefficient question, compare neighboring coefficients using their ratio.
Answer

$n=10$ and $a=3/8$ . The coefficients of $x^2$ and $x^3$ are the only largest coefficients; each is $405/64$ .

Full solution

The coefficient of $x$ is $na=15/4$ .
Equality of the next two coefficients gives
$n(n-1)a^2/2=n(n-1)(n-2)a^3/6.$
All canceled factors are positive because $n\ge3$ and $a>0$ , so $(n-2)a=3$ .
Subtracting this from $na=15/4$ yields $2a=3/4$ , hence $a=3/8$ and $n=10$ .
These values satisfy both original coefficient conditions.

Let $c_k=\binom{10}{k}(3/8)^k$ , for
$0\le k\le10.$
The Binomial Theorem gives $c_{k+1}/c_k=3(10-k)/(8(k+1))$ for $0\le k<10$ .
This ratio exceeds $1$ exactly when $30-3k>8k+8$ , or $k<2$ ; it equals $1$ at $k=2$ and is smaller than $1$ afterward.
Consequently
$c_0<c_1<c_2=c_3>c_4>\cdots>c_{10}.$
The two largest coefficients are therefore precisely $c_2,c_3$ , and
$c_2=45\cdot9/64=405/64.$

Answer

$n=10$ and $a=3/8$ . The coefficients of $x^2$ and $x^3$ are the only largest coefficients; each is $405/64$ .

Key idea

Ratios of neighboring terms can locate a maximum without expanding or computing the entire sequence.
Problem 3: Mark complete
Problem 4 Each term reports an earlier average

Difficulty: 2 of 3 stars, Challenge

A sequence begins with $a_1=2$ . For every integer $n\ge2$ , its $n$ th term is three times the average of all previous terms:
$a_n=\frac{3(a_1+\cdots+a_{n-1})}{n-1}.$
Find an explicit formula for $a_n$ and for $S_N=a_1+\cdots+a_N$ . Prove that your formulas hold for every positive integer index; do not assume a formula for a sum of squares.
1. Hint 1
  Write the defining relation at two consecutive indices and eliminate the earlier partial sum.
2. Hint 2
  Show that $a_{n+1}/a_n=(n+2)/n$ . Look for a product of two consecutive integers.
Answer

$a_n=n(n+1)$ and $S_N=N(N+1)(N+2)/3$ .

Full solution

First
$a_2=3a_1=6.$
For $n\ge2$ , write $(n-1)a_n=3S_{n-1}$ and
$na_{n+1}=3S_n.$
Since $S_n=S_{n-1}+a_n$ , subtracting or substituting gives
$na_{n+1}=(n+2)a_n.$
Thus
$a_{n+1}/a_n=(n+2)/n.$
The same ratio also holds for $n=1$ , because $a_2/a_1=3$ .

This ratio suggests $a_n=n(n+1)$ : it gives the correct first term, and if it holds at $n$ , the recurrence gives
$a_{n+1}=(n+2)a_n/n=(n+1)(n+2).$
Induction proves the formula for every $n$ .
Positivity ensures all ratios used above are legitimate; it also follows directly from the original average rule.

Finally, apply the original relation at index $N+1$ :
$Na_{N+1}=3S_N.$
Substituting the formula for $a_{N+1}$ yields
$S_N=N(N+1)(N+2)/3.$
This obtains the sum from the defining rule itself, rather than importing a separate sum-of-squares identity.
Each next term is determined by earlier ones, so the formulas describe the unique sequence.

Answer

$a_n=n(n+1)$ and $S_N=N(N+1)(N+2)/3$ .

Key idea

When a recurrence contains a partial sum, compare consecutive equations to remove the accumulated history.
Problem 4: Mark complete
Problem 5 A repeating pattern of signs

Difficulty: 2 of 3 stars, Challenge

For a real number $r$ , consider the infinite series whose signs repeat in blocks of two plus signs followed by two minus signs:
$1+r-r^2-r^3+r^4+r^5-r^6-r^7+\cdots.$
Find all real $r$ for which the series converges and has sum $6/5$ . Also explain why substituting $r=1$ into your simplified sum formula does not give the value of the original series.

Builds on Infinite Geometric Series
1. Hint 1
  First determine convergence from the magnitudes of the terms. Within the convergence range, group four consecutive terms.
2. Hint 2
  The four-term block factors as $(1+r)(1-r^2)$ , and the blocks have ratio $r^4$ . Keep the original convergence restriction after canceling factors.
Answer

$r=1/3$ or $r=1/2$ . The sum formula $(1+r)/(1+r^2)$ is valid only for $|r|<1$ ; at $r=1$ the original series diverges.

Full solution

If $|r|\ge1$ , the term magnitudes $|r|^n$ do not approach zero, so the series cannot converge.
If $|r|<1$ , its tails are bounded in absolute value by the corresponding geometric tails, $|r|^{N+1}/(1-|r|)$ , which approach zero.
Thus it converges, and grouping consecutive blocks preserves its sum.

Each block is $r^{4k}(1+r-r^2-r^3)$ .
Summing the geometric series of blocks gives $(1+r-r^2-r^3)/(1-r^4)=(1+r)/(1+r^2)$ , where cancellation is valid because $|r|<1$ .
Equating this to $6/5$ gives
$6r^2-5r+1=(3r-1)(2r-1)=0.$
Both roots $1/3$ and $1/2$ lie in the convergence range, so both are valid.

At $r=1$ , the ordinary partial sums cycle through $1,2,1,0$ and never approach a limit.
The simplified rational expression happens to equal $1$ there, but it was derived only for $|r|<1$ .
Even observing that complete four-term blocks sum to zero would not prove convergence: it examines only one subsequence of partial sums.

Answer

$r=1/3$ or $r=1/2$ . The sum formula $(1+r)/(1+r^2)$ is valid only for $|r|<1$ ; at $r=1$ the original series diverges.

Key idea

Cancellation can extend an algebraic expression to values where the infinite process it represents is still undefined.
Problem 5: Mark complete
Problem 6 Three partial sums in arithmetic order

Difficulty: 2 of 3 stars, Challenge

A geometric sequence has first term $1$ and a nonzero real common ratio $r$ . Write $S_n$ for the sum of its first $n$ terms. Suppose $S_1,S_2,S_4$ , in that order, form an arithmetic sequence.

Find every possible $r$ . For each, determine whether the infinite series converges, and find its sum when it does.

For the convergent case, prove that the terms in positions $1,4,7,10,\ldots$ contribute exactly half the total infinite sum.
1. Hint 1
  Use $2S_2=S_1+S_4$ directly, without dividing by $1-r$ .
2. Hint 2
  Your equation for $r$ simplifies $1+r+r^2$ . Compare each consecutive block of three terms with the first term in that block.
Answer

$r=(-1+\sqrt5)/2$ or $r=(-1-\sqrt5)/2$ . Only the first gives convergence, with sum $(3+\sqrt5)/2$ ; the selected subseries sums to $(3+\sqrt5)/4$ .

Full solution

The arithmetic condition is $2(1+r)=1+(1+r+r^2+r^3)$ , which simplifies to
$r-r^2-r^3=0.$
Since $r\ne0$ , this is $r^2+r-1=0$ , giving the two stated ratios.
Conversely, either root satisfies the original partial-sum relation, so neither can be discarded merely because it is negative.

The positive root lies between $0$ and $1$ because
$2<\sqrt5<3.$
Its geometric series converges and sums to
$1/(1-r)=(3+\sqrt5)/2.$
The negative root is less than $-1$ , so the term magnitudes grow and its series diverges.

For the convergent root, the equation $r+r^2=1$ gives $1+r+r^2=2$ .
Each block $r^{3k}+r^{3k+1}+r^{3k+2}$ therefore equals $2r^{3k}$ .
Summing complete blocks is valid here: both the full series and the subseries have ratios of magnitude below $1$ , and any unfinished tail tends to zero.
Hence the total is twice $1+r^3+r^6+\cdots$ , proving the half-total claim and giving the selected sum $(3+\sqrt5)/4$ .

Answer

$r=(-1+\sqrt5)/2$ or $r=(-1-\sqrt5)/2$ . Only the first gives convergence, with sum $(3+\sqrt5)/2$ ; the selected subseries sums to $(3+\sqrt5)/4$ .

Key idea

A relation among a few partial sums can become an identity for every block of the infinite series.
Problem 6: Mark complete
Problem 7 Local steps and a global total

Difficulty: 2 of 3 stars, Challenge

A finite sequence $a_0,a_1,\ldots,a_{12}$ satisfies $a_0=a_{12}=0$ , $a_k\ge0$ , and $a_{k+1}-a_k\in\{1,-1\}$ for $0\le k<12$ .

Determine every possible value of $S=a_1+a_2+\cdots+a_{11}$ . Identify all sequences attaining the smallest or largest value, and prove that every value in your answer can actually occur.
1. Hint 1
  Compare $a_k$ with its distance in steps from each endpoint. Also determine its parity.
2. Hint 2
  Encode increases as U and decreases as D. Replacing adjacent DU by UD changes only one intermediate height. Starting from the alternating sequence, what does each such replacement do to the total?
Answer

The possible totals are exactly $6,8,10,\ldots,36$ . The unique minimum has $a_k=0$ for even $k$ and $a_k=1$ for odd $k$ ; the unique maximum has $a_k=\min(k,12-k)$ .

Full solution

Each step changes parity, so $a_k$ has the same parity as $k$ .
Since the terms are nonnegative, the six odd-indexed terms are at least $1$ , giving $S\ge6$ .
Equality forces all odd-indexed terms to be $1$ and all even-indexed terms to be $0$ , and this alternating sequence is valid.
The sum $S$ is even because it contains six odd terms and five even terms.

From the initial endpoint, $a_k\le k$ ; from the final endpoint,
$a_k\le12-k.$
Thus $a_k\le\min(k,12-k)$ and
$S\le1+2+\cdots+6+5+\cdots+1=36.$
Equality forces every term to reach its bound, giving the unique sequence that rises for six steps and then falls for six.

It remains to construct every even total between these bounds.
Encode the alternating minimum by UDUDUDUDUDUD.
Whenever adjacent steps are DU, replace them by UD.
This raises just the intermediate height by $2$ , leaves all other heights unchanged, and preserves nonnegativity and the endpoints.
Each swap moves a U past a preceding D, reducing the finite number of such out-of-order pairs by one.
Therefore repeated swaps eventually produce UUUUUUDDDDDD, the maximum sequence.
The total starts at $6$ , increases by exactly $2$ at every swap, and ends at $36$ .
It must therefore pass through every listed value, proving attainability as well as necessity.

Answer

The possible totals are exactly $6,8,10,\ldots,36$ . The unique minimum has $a_k=0$ for even $k$ and $a_k=1$ for odd $k$ ; the unique maximum has $a_k=\min(k,12-k)$ .

Key idea

Bounds and parity restrict possible totals; a controlled local move can prove that none of the remaining values are missing.
Problem 7: Mark complete
Problem 8 When two infinite codes agree

Difficulty: 3 of 3 stars, Deep challenge

A binary code $d_1,d_2,\ldots$ , with every $d_n$ equal to $0$ or $1$ , represents the real number $V(d)=\sum_{n=1}^{\infty}d_n/2^n$ .

Give a complete description of when two distinct binary codes represent the same number. Prove your description by examining their first differing position.

Consequently, determine exactly which numbers in $[0,1]$ have two such codes, and prove that no number has more than two. Explain the endpoint cases $0$ and $1$ .

Builds on Infinite Geometric Series
1. Hint 1
  If the first difference is at position $m$ , the contribution there has magnitude $2^{-m}$ . What is the largest contribution all later positions can make?
2. Hint 2
  Equality in the geometric tail bound forces every later digit in one code to be $1$ and every later digit in the other to be $0$ .
Answer

Two codes agree in value exactly when, after a common prefix, one has $1$ followed entirely by $0$ s and the other has $0$ followed entirely by $1$ s. Exactly the numbers $j/2^m$ with integers $m\ge1$ and $0<j<2^m$ have two codes. The endpoints each have one.

Full solution

Every code defines a convergent sum: the contribution after position $N$ is between $0$ and the geometric tail $\sum_{n>N}2^{-n}=2^{-N}$ , which tends to zero.
Suppose two distinct codes first differ at position $m$ , with $d_m=1$ and $e_m=0$ .
If their values agree, then

$2^{-m}=\sum_{n>m}\frac{e_n-d_n}{2^n}\le\sum_{n>m}\frac1{2^n}=2^{-m}.$

Equality forces $e_n-d_n=1$ at every later position: any smaller digit difference would create a positive deficit that no other position can exceed its bound to repair.
Thus $d$ has only $0$ s afterward and $e$ only $1$ s.
Conversely, these tails have exactly the required difference, so this pattern always gives equal values.

The code with the $1$ at position $m$ terminates, so its value is an interior fraction $j/2^m$ .
Every such fraction has a finite binary representation: repeatedly divide the integer $j$ by $2$ , recording each remainder $0$ or $1$ , then read the remainders in reverse order and divide the resulting finite binary integer by $2^m$ .
Replace its last $1$ by $0$ and all later digits by $1$ to obtain a second code.
A terminating code can match a distinct code only by changing its last $1$ : changing an earlier position would violate the forced all-zero tail, and changing a later position is impossible.
Hence it has exactly one partner, and the first-difference argument shows that any repeated value has this terminating code.
No value has three codes.
Finally, $0$ requires all digits $0$ , and $1$ requires all digits $1$ , so neither endpoint has a partner in this indexing convention.

Answer

Two codes agree in value exactly when, after a common prefix, one has $1$ followed entirely by $0$ s and the other has $0$ followed entirely by $1$ s. Exactly the numbers $j/2^m$ with integers $m\ge1$ and $0<j<2^m$ have two codes. The endpoints each have one.

Key idea

An equality case in an infinite tail bound can classify all ambiguities in a numerical representation.
Problem 8: Mark complete
Problem 9 Every third coefficient

Difficulty: 3 of 3 stars, Deep challenge

Let $m$ be a positive integer. In the expansion of $(1+x)^{6m}$ , add the coefficients of $x^0,x^3,x^6,\ldots,x^{6m}$ . Find a closed formula for this sum and prove it without expanding all the terms.

You may use complex numbers, but do not use trigonometric forms or De Moivre's theorem. Derive the algebraic identities you need.
1. Hint 1
  Try evaluating the polynomial at $1$ and at the two nonreal roots of $z^2+z+1=0$ .
2. Hint 2
  For $\omega=(-1+i\sqrt3)/2$ , show that $1+\omega^k+\omega^{2k}$ is $3$ when $3$ divides $k$ and $0$ otherwise. Then find $(1+\omega)^6$ .
Answer

The sum is $(2^{6m}+2)/3$ .

Full solution

Let
$\omega=(-1+i\sqrt3)/2.$
Direct substitution gives $\omega^2+\omega+1=0$ , so $(\omega-1)(\omega^2+\omega+1)=\omega^3-1=0$ and hence
$\omega^3=1.$
Since $\omega\ne1$ , its powers repeat as $1,\omega,\omega^2$ .
It follows that $1+\omega^k+\omega^{2k}$ equals $3$ if $3$ divides $k$ , and otherwise equals
$1+\omega+\omega^2=0.$

Write
$P(x)=(1+x)^{6m}=\sum_{k=0}^{6m}c_kx^k.$
Then $P(1)+P(\omega)+P(\omega^2)=\sum c_k(1+\omega^k+\omega^{2k})$ , which is exactly three times the desired coefficient sum.
This finite identity needs no convergence argument.

Now
$P(1)=2^{6m}.$
Also $1+\omega=-\omega^2$ , so
$(1+\omega)^6=\omega^{12}=1.$
Similarly, $1+\omega^2=-\omega$ , so
$(1+\omega^2)^6=1.$
Therefore $P(\omega)=P(\omega^2)=1$ , and division by $3$ gives $(2^{6m}+2)/3$ .
The calculation explains why these three evaluations retain exactly the powers divisible by $3$ while canceling the others.

Answer

The sum is $(2^{6m}+2)/3$ .

Key idea

Evaluating at roots of a simple algebraic equation can isolate selected coefficients of a polynomial.
Problem 9: Mark complete
Problem 10 Powers just below integers

Difficulty: 3 of 3 stars, Deep challenge

Let $A=2+\sqrt3$ . For $n\ge1$ , let $b_n$ be the greatest integer not exceeding $A^n$ . Prove that every $b_n$ is odd, and find a recurrence expressing $b_{n+2}$ in terms of $b_{n+1}$ and $b_n$ , together with the required initial terms.

Let $c_n$ be the least integer greater than or equal to $A^n$ . Determine the exact value of $\sum_{n=1}^{\infty}(c_n-A^n)$ , and justify convergence. No decimal approximations to the powers are allowed.

Builds on Infinite Geometric Series
1. Hint 1
  Pair $A$ with its conjugate $B=2-\sqrt3$ , which satisfies $0<B<1$ . Apply the Binomial Theorem to $A^n+B^n$ .
2. Hint 2
  The conjugate sum is an even integer, while $B^n$ lies strictly between $0$ and $1$ . Also $A+B=4$ and $AB=1$ .
Answer

$b_1=3$ , $b_2=13$ , and $b_{n+2}=4b_{n+1}-b_n+2$ for $n\ge1$ ; every $b_n$ is odd. The infinite sum is $(\sqrt3-1)/2$ .

Full solution

Put $B=2-\sqrt3$ , so $0<B<1$ .
The Binomial Theorem shows that $T_n=A^n+B^n$ is an even integer: the terms containing odd powers of $\sqrt3$ cancel, and every remaining term is twice an integer.
Since $A^n=T_n-B^n$ and $0<B^n<1$ , we have
$T_n-1<A^n<T_n.$
Thus $b_n=T_n-1$ is odd and $c_n=T_n$ .
The strict inequalities also prove that no $A^n$ is an integer.

Both $A$ and $B$ satisfy
$z^2-4z+1=0.$
Multiplying by $z^n$ and adding the resulting identities gives
$T_{n+2}=4T_{n+1}-T_n.$
Substituting $T_n=b_n+1$ yields
$b_{n+2}=4b_{n+1}-b_n+2.$
Directly, $T_1=4$ and $T_2=(A+B)^2-2AB=14$ , so $b_1=3$ and $b_2=13$ .

Finally,
$c_n-A^n=B^n.$
The desired sum is therefore geometric, with ratio $B$ strictly between $0$ and $1$ .
Its tail after $N$ terms is $B^{N+1}/(1-B)$ , which tends to zero, so convergence is justified.
Its value is
$B/(1-B)=(2-\sqrt3)/(\sqrt3-1)=(\sqrt3-1)/2.$

Answer

$b_1=3$ , $b_2=13$ , and $b_{n+2}=4b_{n+1}-b_n+2$ for $n\ge1$ ; every $b_n$ is odd. The infinite sum is $(\sqrt3-1)/2$ .

Key idea

Conjugate powers can separate an exact integer from a small positive error, revealing both a recurrence and an infinite sum.
Problem 10: Mark complete