Argument over an induction proof 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!


*

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

*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.
 A: 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.
A: 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.
