Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been working on this for a while now and I can't seem to get anywhere. Could anyone help me out or walk me through a solution? Any help at all would be wonderful. Thank you.

Find a, b such that $Fn = a( \frac {1 + \sqrt 5}{2})^n + b( \frac {1 - \sqrt5}{2})^n$ for every $n ∈ \mathbb N$. Prove by induction that this is true for $Fn$ is correct for every $n ∈ \mathbb N$.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

To find $a$ and $b$, just substitute $n=0$ and $n=1$ into the equation

$$F_n=a\left(\frac{1+\sqrt5}2\right)^n+b\left(\frac{1-\sqrt5}2\right)^n$$

to get two equations in the two unknowns $a$ and $b$. $F_0=0$ and $F_1=1$, so you get this system:

$$\left\{\begin{align*} &a+b=0\\\\ &\left(\frac{1+\sqrt5}2\right)a+\left(\frac{1-\sqrt5}2\right)b=1\;. \end{align*}\right.$$

The second equation may look a little ugly, but the system is actually very easy to solve, and the solution isn’t very ugly.

Once you have $a$ and $b$, you have to show by induction that if we define

$$x_n=a\left(\frac{1+\sqrt5}2\right)^n+b\left(\frac{1-\sqrt5}2\right)^n\;,$$

then $F_n=x_n$ for all $n\ge 0$. This will certainly be true for $n=0$ and $n=1$, since you used those values of $F_n$ to get $a$ and $b$ in the first place. To finish the job, you’ll have the induction hypothesis that $F_k=x_k$ for all $k\le n$ (for some $n\ge 1$, and your induction step will be showing that $F_{n+1}=x_{n+1}$. Of course you know that $F_{n+1}=F_n+F_{n-1}$, and your induction hypothesis tells you that $F_n+F_{n-1}=x_n+x_{n-1}$, so your task will really be to prove that $x_n+x_{n-1}=x_{n+1}$ for the particular $a$ and $b$ that you found initially. If you have the right $a$ and $b$, this is fairly straightforward algebra.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.