Proof $a_{n}$ by induction

Question

This topic is a continuation of Prove that $a_{n} = a_{n-1} + a_{n-2}$.

I need to prove that $a_{n} = (\frac{5+3\sqrt{5}}{10})(\frac{1+\sqrt{5}}{2})^{n} + (\frac{5-3\sqrt{5}}{10})(\frac{1-\sqrt{5}}{2})^{n}$ for all $n \geq 1$.

This is how I tried to prove this.

Basic step: $a_{1} = (\frac{5+3\sqrt{5}}{10})(\frac{1+\sqrt{5}}{2})^{1} + (\frac{5-3\sqrt{5}}{10})(\frac{1-\sqrt{5}}{2})^{1}$ which is equal to $2$ and is correct.

Inductive step: Let $k \geq 1$ and let the statement apply to each $k$ where $1 \geq j \geq k$. From the previous topic we know that $a_{k} = a_{k-1} + a_{k-2}$ and so that $a_{k+1} = a_{k} + a_{k-1}$. Because of the hypothesis we know that the statement applies for $a_{k}$ and $a_{k-1}$. As $a_{k+1}$ exists of the sum of $a_{k}$ and $a_{k-1}$, we can conclude that the statement also applies for $a_{k+1}$.

Is this proof by induction valid?

Answer 1

Rather than solve the problem through the standard methods for more general linear recurrences, I'll address your questions about induction:

1. Your choice of induction hypothesis is right. We already know that $a_{n+2}=a_{n+1}+a_n$ for all $n\geq 1$ from your previous question. Here you want to assume that $a_{n+1}$ and $a_n$ can be written explicitly as $$a_{n+1}=\left(\frac{5+3\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} + \left(\frac{5-3\sqrt{5}}{10}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}$$ and $$a_n=\left(\frac{5+3\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{n} + \left(\frac{5-3\sqrt{5}}{10}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n}$$ respectively. Using that and the fact that $a_{n+2}=a_{n+1}+a_n$ you want to show that $a_{n+2}$ can be written in the same way, only with $n+2$ in the corresponding exponents. This is a matter of simple algebraic manipulation: write out the sum, factor out $\lambda_\pm=\frac{1\pm\sqrt 5}{2}$ and note that these numbers are roots of $x^2=x+1$ as @lhf pointed out.

2. That brings us to the following problem: when $n=1$, we have $a_3=a_2+a_1$. This means that $a_1$ is not the only base case: you need to prove $a_2$ as a base case as well. More generally: if your inductive step $P(n)$ depends on $P(n-1),P(n-2),...,P(n-k)$, then you need to prove $k$ base cases. See the Wikipedia page on strong induction.

Answer 2

We have $a_{n} = a_{n-1} + a_{n-2}$ with $a_{0} = 1$ and $a_{1}=2$.

Let $b_{n} = (\frac{5+3\sqrt{5}}{10})(\frac{1+\sqrt{5}}{2})^{n} + (\frac{5-3\sqrt{5}}{10})(\frac{1-\sqrt{5}}{2})^{n}$.

To prove that $a_n=b_n$, it is enough to prove that $b_{n} = b_{n-1} + b_{n-2}$ with $b_{0} = 1$ and $b_{1}=2$.

• $b_{0} = 1$ and $b_{1}=2$ is immediate.

• $b_{n} = b_{n-1} + b_{n-2}$ follows from the fact that $\frac{1\pm\sqrt{5}}{2} $ are roots of $x^2=x+1$.