# Fibonacci problem, proof by induction?

• Nov 13th 2012, 09:27 PM
ZPgamer
Fibonacci problem, proof by induction?
Given:
alpha = (1+ sqrt5)/2 and beta = (1-sqrt5)/2
alpha^2 = 1 + alpha and beta^2 = 1+ beta

Use induction to prove that for all integers n >= 1 we have
alpha^n = f(n-1)+ f(n)*(alpha) and beta^n = f(n-1)+ f(n)*(beta)

I've did my base case and plug in k+1 to n but I can't get them equal to each other. Please help, I've been playing with these numbers for hours.
• Nov 13th 2012, 09:46 PM
MarkFL
Re: Fibonacci problem, proof by induction?
Having demonstrated the base case $\displaystyle P_1$ is true, then state the induction hypothesis $\displaystyle P_k$

$\displaystyle \alpha^k=F_{k-1}+F_{k}\alpha$

Multiply through by $\displaystyle \alpha$:

$\displaystyle \alpha^{k+1}=F_{k-1}\alpha+F_{k}\alpha^2$

$\displaystyle \alpha^{k+1}=F_{k-1}\alpha+F_{k}(1+\alpha)$

$\displaystyle \alpha^{k+1}=(F_{k}+F_{k-1})\alpha+F_{k}$

Now, since $\displaystyle F_{n+1}=F_{n}+F_{n-1}$, can you continue?
• Nov 13th 2012, 10:01 PM
ZPgamer
Re: Fibonacci problem, proof by induction?
so alpha^(k+1) = (alpha)*f(k+1) + f(k)
sorry, I still don't know how is this a proof alpha^n = f(n-1)+ f(n)*(alpha)
• Nov 13th 2012, 10:19 PM
MarkFL
Re: Fibonacci problem, proof by induction?
We may write this result as:

$\displaystyle \alpha^{k+1}=F_{(k+1)-1}+F_{k+1}\alpha$

You see, we have arrived at $\displaystyle P_{k+1}$ which we derived from $\displaystyle P_k$, completing the proof by induction.

Observe that this is the same as the induction hypothesis, except $\displaystyle k$ is replaced with $\displaystyle k+1$. This means it is true for all $\displaystyle n\in\mathbb{N}$.

Have you learned the analogy of climbing a ladder or falling dominoes to mathematical induction?
• Nov 13th 2012, 10:34 PM
ZPgamer
Re: Fibonacci problem, proof by induction?
oh okay, thanks. This problem is just very different to the kind of Fibonacci problem I've been doing. But they're just the same in the end. Thanks again : )
• Nov 13th 2012, 10:38 PM
MarkFL
Re: Fibonacci problem, proof by induction?
Glad to help, and welcome to the forum! :)