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.:)
 
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Thread 'Imaginary Pythagoras'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...

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