# Thread: Fibonacci problem, proof by induction?

1. ## 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.

2. ## 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?

3. ## 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)

4. ## 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?

5. ## 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 : )

6. ## Re: Fibonacci problem, proof by induction?

Glad to help, and welcome to the forum!