MHB Prove $(c_n)^3=d_{3n}: Sequence Challenge

AI Thread Summary
The sequences \( (c_n)_n \) and \( (d_n)_n \) are defined with specific recurrence relations, leading to the claim that \( c_n = f_{3n} \), where \( f_n \) represents Fibonacci numbers. An inductive proof confirms this relationship, establishing that \( c_{n+1} \) aligns with \( f_{3n+3} \). Additionally, it is shown that \( d_n = (f_n)^3 \) through a separate inductive argument, utilizing properties of Fibonacci numbers and matrix exponentiation. Ultimately, the conclusion is reached that \( (c_n)^3 = d_{3n} \), affirming the relationship between these sequences.
anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
Consider the sequences $(c_n)_n,\,(d_n)_n$ defined by

$c_0=0$, $c_1=2$, $c_{n+1}=4c_n+c_{n-1}$, $n \ge 0$,

$d_0=0$, $d_1=1$, $d_{n+1}=c_n-d_n+d_{n-1}$, $n \ge 0$.

Prove that $(c_n)^3=d_{3n}$ for all $n$.
 
Mathematics news on Phys.org
[sp]These sequences are Fibonacci-related. Let $f_n$ be the $n$th Fibonacci number, with $f_0=0$, $f_1 = 1$, and $f_{n+1} = f_n + f_{n-1}$ for $n\geqslant1$.

First claim: $c_n = f_{3n}$.

Proof (by induction): The claim is true for $n=0$ and $n=1$. Suppose it is true for $n$ and $n-1$. Then $$\begin{aligned}c_{n+1} &= 4f_{3n} + f_{3n-3}\\ &= 4f_{3n} + (f_{3n-1} - f_{3n-2}) \\ &= 4f_{3n} + f_{3n-1} - (f_{3n} - f_{3n-1}) \\ &= 3f_{3n} + 2(f_{3n+1} - f_{3n}) \\ &= 2f_{3n+1} + (f_{3n+2} - f_{3n+1} \\ &= f_{3n+2} + f_{3n+1} = f_{3n+3}.\end{aligned}$$ That completes the inductive step.

Thus the recurrence relation for $d_n$ becomes $d_{n+1} = f_{3n} - d_n + d_{n-1}$.

Second claim: $d_n = (f_n)^3$.

Proof: This proof is also by induction, but it requires a bit of preliminary work on Fibonacci numbers. To get at $(f_n)^3$ it is easiest to use the fact that if $A$ is the matrix $\begin{bmatrix}1&1 \\ 1&0\end{bmatrix}$, then $A^n = \begin{bmatrix}f_{n+1}&f_n \\ f_n&f_{n-1} \end{bmatrix}.$ Using the fact that $A^{3n} = \bigl(A^n\bigr)^3$, you can check that $f_{3n} = 2f_n^3 + 3f_{n-1}f_nf_{n+1}.$ (See here for details.) Next, notice that $$\begin{aligned}f_{n+1}^3 &= (f_n + f_{n-1})^3 \\ &= f_n^3 + 3f_{n-1}f_n(f_n + f_{n-1}) + f_{n-1}^3 \\ &= f_n^3 + 3f_{n-1}f_nf_{n+1} + f_{n-1}^3 \\ &= (2f_n^3 + 3f_{n-1}f_nf_{n+1}) - f_n^3 + f_{n-1}^3 \\ &= f_{3n} - f_n^3 + f_{n-1}^3. \end{aligned}$$ But that is exactly the inductive step required to show that $d_n = (f_n)^3$.

Conclusion: $(c_n)^3=d_{3n} = f_{3n}^3$.[/sp]
 
Last edited:
Thanks for participating, Opalg! Yes, it seems induction is the only viable option to tackle this problem.:)
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...

Similar threads

Replies
3
Views
2K
Replies
1
Views
2K
Replies
8
Views
3K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
4
Views
2K
Replies
1
Views
2K
Back
Top