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

[anemone]

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$.

 

[Opalg]

[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]

 

[anemone]

Thanks for participating, Opalg! Yes, it seems induction is the only viable option to tackle this problem.:)