Argument over an induction proof

Question

My friend gave me a problem.

Define a sequence $\langle a_n \rangle$ by the recurrence relation :$$ a_{n+2} - 6a_{n+1} + 8a_n = 0 $$ and $a_1 = 4, a_2 = 8 $. Find the general term $a_n$ in closed form.

By inspection, I got the general term as $ a_n = 2^{n+1} $. Then I proved it using induction. However, he says that the proof isn't elegant!

1. He questions the source of my induction hypothesis: "how did you get that in the first place?".

2. He says that he is fine with the induction proof, but he isn't satisfied. He asks as to how I know that $a_n = 2^{n+1} $ is the only solution.

We had a heated argument over this matter. Now, what's wrong with what I did?!?

---

Btw, my proof:

Hypothesis: $P(n)$ = " $a_n = 2^{n+1} $ is the $n$*th* term of the given sequence."

Assumption: Assume that $ P(i),\; \forall\; i \in \{1,2,...k-1\} $ to be true.

To prove $P(k)$:

We know that $a_k = 6a_{k-1} - 8a_{k-2}$. Also, from our assumption, we have $a_{k-1} = 2^k$ and $a_{k-2} = 2^{k-1}$. Plugging that in the relation gives us $a_k = 2^{k+1}$.

Conclusion: $P(k)$ is true if $ P(i),\; \forall\; i \in \{1,2,...k-1\} $. $P(1)$ is true. So $P(2)$ is true, and so on.

Therefore, $P(n)$ is true $\forall\; n \in \mathbb{N}$.

Hence proved.

Answer 1

Except for minor formulation quibbles, your proof is a valid proof that $2^{n+1}$ is the only solution to the recurrence.

The minor quibble is that instead of making your induction hypothesis be "$a_n=2^{n+1}$ is the $n$th term of the given sequence", it would be more rigorous to make it "If $(a_k)_{k\ge 1}$ is any sequence that satisfies the recurrence, then $a_n=2^{n+1}$". Then what you have is a proof by induction on $n$ that every sequence that satisfies your recurrence is equal to the particular sequence $2^{n+1}$.

Strictly speaking you also need to prove that $2^{n+1}$ is a solution at all (because your induction proof assumes that you already have a sequence that solves the recurrence). But that proof is as simple as plugging $2^{n+1}$ into the recurrence relation and simplifying. No induction is needed there.

Answer 2

Finding the closed form of a recurrence relation always involves some guessing; in the case of a relation like $$ a_{n+2}+ba_{n+1}+ca_{n}=0 $$ one can, as a first approximation, try finding whether $x^n$ can be used. It can if, for all $n$, $$ x^{n+2}+bx^{n+1}+cx^n=0. $$ Excluding $x=0$ that would be trivial and surely doesn't satisfy your initial conditions, we get $$ x^2+bx+c=0. $$

Oh! Wait! In our case this means $x^2-6x+8=0$, that is $x=2$ or $x=4$.

Now, if $\langle a_n\rangle$ and $\langle b_n\rangle$ satisfy the general recurrence (no initial condition, for the moment), also $\langle\alpha a_n+\beta b_n\rangle$ satisfies it. So we can try $$ a_n=\alpha\cdot 2^n + \beta\cdot 4^n $$ Setting $a_1=4$ and $a_2=8$ we get \begin{cases} 2\alpha+4\beta=4\\ 4\alpha+16\beta=8 \end{cases} and this implies $\alpha=2$ and $\beta=0$.

Hey! I did it! My closed form is $a_n=2\cdot 2^n=2^{n+1}$. It surely satisfies our conditions and there is at most one sequence satisfying them, because once you know $a_1$ and $a_2$, you know $a_3=6a_2-8a_1$; then you know $a_4=6a_3-8a_4$ and so on.

End of the story! If you have a recurrence relation of the form $$ a_{n+k}+b_1a_{n+k-1}+\dots+b_ka_n=0 $$ and the polynomial $$ x^k+b_1x^k+\dots+b_{k-1}x+b_k $$ has $k$ distinct real roots $r_1,r_2,\dots,r_k$, then any sequence satisfying the recurrence relation is of the form $$ a_n=\alpha_1 r_1^n+\alpha_2 r_2^n+\dots+\alpha_k r_k^n $$ and you can determine $\alpha_1,\dots,\alpha_k$ by the $k$ initial conditions.

It's a bit more complicated with complex roots or repeated roots, but not really too much.