A calculus proof for the general term of the Fibonacci sequence [duplicate]

This question already has an answer here:

Let $a_0=1$,$a_1=1$ and $a_n=a_{n-1} + a_{n-2}$ for $n \geq 2$, I would like to prove: $$a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n + 1}- \left(\frac{1-\sqrt{5}}{2}\right)^{n + 1} \right)$$ for $n\in \mathbb{N^*}$.

I used induction to prove it (not sure if it is a correct way), is there a way to find it doing some calculus ? I couldn't come to that result.

marked as duplicate by Martin Sleziak, user147263, Robert Soupe, Travis Willse, Jonas MeyerFeb 2 '15 at 21:45

• I don't think it's a duplicate, OP asks specifically for a calculus proof. – Najib Idrissi Jan 19 '15 at 19:22
• it seems that induction is the calculus proof\ – GorillaApe Jan 19 '15 at 19:52
• Since you mentioned using induction, these posts can also be interesting for you: math.stackexchange.com/questions/886978/…, math.stackexchange.com/questions/894873/… (Probably you can find more posts like that.) – Martin Sleziak Jan 22 '15 at 8:27
• According to the convention $a_{0} = 1, a_{1} = 1$ we must have the exponents $(n + 1)$ in the formula instead of $n$. I have taken liberty to fix it. If instead we have $a_{0} = 0, a_{1} = 1$ then the exponents remain as $n$. – Paramanand Singh Jan 22 '15 at 14:09
• If we start as you did, the Fibonacci numbers are the coefficients of $x^n$ in the Maclaurin expansion of $\frac{1}{1-x-x^2}$. If in the more current syle, we start with $F_0=0$, use $\frac{x}{1-x-x^2}$. Then we can use partial fractions to obtain the formula. – André Nicolas Jan 30 '15 at 4:19

The characteristic equation $r^2=r+1$ has the roots $r_1=\frac{1+\sqrt 5}{2}$ and $r_2=\frac{1-\sqrt 5}{2}$ so

$$a_n=a r_1^n+br_2^n$$ and $a$ and $b$ are easily determined using the initial conditions.

• where did characteristic equation came from ? – GorillaApe Jan 19 '15 at 19:03
• If we look for a solution of the given recursive sequence on the form $a_n=r^n$ then we get the characteristic equation. – user63181 Jan 19 '15 at 19:06

You probably know that this is the famous Fibonacci sequence $$1,1,2,3,5,8,13,...$$

One way to derive this formula is to use linear algebra. Note that you can write this recurrence relation in the form $b_n = a_{n+1}$, and $b_{n+1} = a_{n+2} = a_{n+1} + a_n = a_n + b_n$. This means that we can write the linear recurrence $$\left(\begin{array}{c}a_{n+1}\\b_{n+1}\end{array}\right)=\left(\begin{array}{cc}0&1\\1&1\end{array}\right)\left(\begin{array}{c}a_{n}\\b_{n}\end{array}\right),$$ and this implies that $$\left(\begin{array}{c}a_{n}\\b_{n}\end{array}\right)=\left(\begin{array}{cc}0&1\\1&1\end{array}\right)^n\left(\begin{array}{c}a_{0}\\b_{0}\end{array}\right).$$ You are given that $(a_0,b_0) = (1,1)$, so you just need to compute the first component of $$\left(\begin{array}{cc}0&1\\1&1\end{array}\right)^n\left(\begin{array}{c}1\\1\end{array}\right).$$

Well there is no specific proof which makes use of calculus (meaning differentiation / integration) however there is a proof which does involve analysis in an indirect way. Here it goes.

The basic fact from analysis will be some concepts related to power series. A power series of type $\sum a_{n}x^{n}$ has a radius of convergence $R \geq 0$ such that the series is convergent if $|x| < R$ and divergent if $|x| > R$. The power series defines a continuous and infinitely differentiable function $f(x)$ for $|x| < R$. Also if two power series $\sum a_{n}x^{n}$ and $\sum b_{n}x^{n}$ are such that they are equal for all values of $x$ in some interval $(-R, R)$, then $a_{n} = b_{n}$ for all non-negative integers $n$. This last fact will be the main idea used in this proof.

Let $a_{n}$ denote $n^{\text{th}}$ Fibonacci number and consider the power series $F(x) = \sum_{n = 0}^{\infty}a_{n}x^{n}$. Clearly we can see that if this series converges in certain interval $(-R, R)$ then we have the following relations for $|x| < R$: $$F(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + \cdots\tag{1}$$$$xF(x) = a_{0}x + a_{1}x^{2} + a_{2}x^{3} + \cdots \tag{2}$$$$x^{2}F(x) = a_{0}x^{2} + a_{1}x^{3} + a_{2}x^{4} + \cdots\tag{3}$$ Now these equations clearly give us $$F(x) - xF(x) - x^{2}F(x) = a_{0} + (a_{1} - a_{0})x$$ as rest of the terms cancel because of the recurrence relation $a_{n + 2} = a_{n + 1} + a_{n}$. Putting $a_{0} = 1, a_{1} = 1$ we get $$F(x) = \frac{1}{1 - x - x^{2}}$$ If $\alpha = (1 + \sqrt{5})/2, \beta = (1 - \sqrt{5})/2$ then $\alpha, \beta$ are roots of $t^{2} - t - 1 = 0$ and hence we can write $$1 - x - x^{2} = (1 - \alpha x)(1 - \beta x)$$ Thus we have $$F(x) = \frac{1}{(1 - \alpha x)(1 - \beta x)} = \frac{A}{1 - \alpha x} + \frac{B}{1 - \beta x}$$ where $A, B$ need to be found out. Clearly we have $$1 = A(1 - \beta x) + B(1 - \alpha x)$$ and putting $x = 1/\alpha$ we get $A = \dfrac{\alpha}{\alpha - \beta}$. Similarly $B = -\dfrac{\beta}{\alpha - \beta}$. Thus we have $$F(x) = \frac{1}{\alpha - \beta}\left(\frac{\alpha}{1 - \alpha x} - \frac{\beta}{1 - \beta x}\right)\tag{4}$$ Next we use another result from power series namely that $$\frac{1}{1 - x} = 1 + x + x^{2} + x^{3} + \cdots$$ for $|x| < 1$. Using this result we can see that $$\sum_{n = 0}^{\infty}a_{n}x^{n} = F(x) = \frac{1}{\alpha - \beta}\left(\sum_{n = 0}^{\infty}(\alpha^{n + 1} - \beta^{n + 1})x^{n}\right)$$ and hence the coefficients in both power series must be equal and we have $$a_{n} = \frac{\alpha^{n + 1} - \beta^{n + 1}}{\alpha - \beta} = \frac{1}{\sqrt{5}}\left\{\left(\frac{1 + \sqrt{5}}{2}\right)^{n + 1} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n + 1}\right\}$$

Let's $\phi =\frac{1+ \sqrt{5}}{2} \;$, and $\psi =\frac{1- \sqrt{5}}{2}$.

Using induction, prove $\phi^n = F_{n-1} + F_n \phi \;$, & $\psi^n = F_{n-1} + F_n \psi$. (1)

Therefore, $\Large{\phi^n - \psi^n = F_n (\phi - \psi) = F_n \sqrt{5}} \;$. (2)

So,

$$\LARGE{F_n = \frac1{\sqrt5} (\phi^n - \psi^n) } \;$$

$\\$

Also, $\phi^n + \psi^n = 2F_{n-1} + F_n (\phi + \psi) = 2F_{n-1} + F_n = F_{n-1} + F_{n+1}$ (3)

Note: $\phi^2 = \phi + 1 \;$, therefore $\; \phi^3 = \phi^2 + \phi = 2 \phi + 1 \;$, and so on... By using induction you can prove (1).