# Homework Help: Fibonacci Number Crunch

1. Mar 28, 2006

### moo5003

Basically my problem comes down to an algebra thing. This is a proofs class and I'm trying to show using strong induction that the fionacci numbers to the nth power can be given by the formula

1 / Radical (5) [ (1+Rad(5) / 2) ^ n - (1-Rad(5) / 2) ^ n.

My problem comes down to the induction step.. after substiting the assumed for f(n) and f(n-1) and adding those to equal f(n+1) I have no clue how to get the equation given by f(n) + f(n-1) represent the above witn n+1 as the powers instead of n. Any help here would be greatly appreciated.

2. Mar 28, 2006

### AKG

Hint:

$$\frac{1\pm\sqrt{5}}{2}$$

are the solutions to x² - x - 1 = 0, so they satisfy x+1 = x². Anyways, please use LaTeX and show your work, because this problem is quite straightforward, so it's hard to guess where you're getting stuck. Therefore, it's hard to know what hint to give that will be useful but won't give too much away.

Last edited: Mar 28, 2006