Is this recursion relation proof correct? Recurrence relation:$$a_0 = 1$$
$$a_{n+1} = 2a_n$$
I'm trying to prove that for any n ∈ N, $a_n = 2^n$.  I want to use induction.
What I have is, assume that $a_n = 2^n$ is true for $P(n)$.
Then $P(n+1)$ would be:
$$a_{n+1} = 2^{n+1}$$
$$a_{n+1}=2\cdot(2^n)$$
Because $a_n = 2^n$, then we can substitute, so $a_{n+1} = 2a_n$.
 A: The idea of the proof is certainly correct. There are some issues, such as the incorrect but unnnecessary assertion that all even numbers are powers of $2$.
We rewrite the proof you gave, making small modifications. After a while, you will not be expected to use the notation $P(n)$ explicitly. 
Let $P(n)$ be the assertion that $a_n=2^n$. We prove by induction that $P(n)$ is true for every non-negative integer $n$.
Certainly $P(0)$ is true, since $a_0=1=2^0$.
Suppose that for a particular integer $k$, the assertion $P(k)$ is true. We show that $P(k+1)$ is true.
Since $P(k)$ is true, we have $a_k=2^k$. But then 
$$a_{k+1}=2a_k=2\cdot 2^k =2^{k+1},$$
so $P(k+1)$ is true. This completes the induction step and the proof. 
A: The key to an induction proof is to prove $P(0)$ and then prove that $P(n)\implies P(n+1)$.
$P(0)$ is just the statement that $a_0=2^0$, which is obvious.
Now assume you know $P(n)$ - that is, $a_n = 2^{n}$. Then $a_{n+1}=2a_n = 2(2^n)=2^{n+1}$. Therefore you know $P(n+1)$.
Therefore you are done.
There is nothing needed about even numbers in this proof, just that $2(2^n)=2^{n+1}$.
