# 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 $P_1$ is true, then state the induction hypothesis $P_k$

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

Multiply through by $\alpha$:

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

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

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

Now, since $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:

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

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

Observe that this is the same as the induction hypothesis, except $k$ is replaced with $k+1$. This means it is true for all $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!