Prove by induction that $a_{n+1} = a_{n} + a_{n}$

Question

I flip a fair coin $n$ times, the amount of possible outcomes is $2^n$. I'm trying to prove that the number of possible combinations that result in an even amount of heads after $n+1$ flips is equal to $a_{n} + a_{n}$

Outcomes with even amount of heads
$a_{0} = 1$
$a_{1} = 2$
$a_{2} = 4$

I thought about proving this by induction, but I get stuck right after the base case.

My attempt look something like this,

Prove that $a_{n+1} = a_{n} + a_{n} $

Base case: We test if the condition is true for $n=0$

$a_{1} = a_{0} + a_{0} = 1 + 1 = 2$

The condition is true for $n=0$

Induction step: Assume that the condition is true for $n=p$ where $p$ is a positive integer.
Prove that the condition is true for $n=p+1$

$a_{p+1} =$

And this is where I get stuck...

Can I prove the condition true by induction or should I approach this in another way? Help is appreciated (:

---

Edit

Okay, I have redefined my question to something that I hope makes more sense.

I will try to prove that if I flip a fair coin $n$ times ($2^{n}$ possible outcomes), there is always $2^{n-1}$ possible outcomes with an even amount of heads.

The total amount of possible outcomes is $2^{n}$

Now, the condition I want to prove true is the following:

$n+1$ flips will result in $2^{n}$ outcomes with an even amount of heads. This is the same as saying that half of all possible outcomes will have an even amount of heads. But I can't know this until it has been proven.

I will attempt to prove this by induction.

I make the assumption that $n$ flips will result in $2^{n-1}$ outcomes with an even amount of heads.

Base case: $1$ flip ($n=0$)

$2^{0} = 1$ The condition is true for the base case.

Induction step:

This is where I get stuck, not entirely sure on how to start it.

Answer 1

You can perhaps look at this as follows: any combination of $\;p+1\;$ flips stems from a combination of $\;p\;$ flips after which you can get either head of tails, from which it follows that the total ammount is twice the ammoun of $\;p\;$ flips

Answer 2

The induction step would be to say assume we have shown that $a_k=2^{k-1}$. We want to prove that $a_{k+1}=2^k$. As you have shown that $a_{k+1}=a_k+a_k$, you can say $a_{k+1}=2^{k-1}+2^{k-1}=2^k$. That is the usual structure of an induction proof-you compute $a_{k+1}$ from $a_k$, substitute in the known value of $a_k$, and show $a_{k+1}$ is what you claim.

Answer 3

Say that after $n$ tosses, you have $e_n$ even amounts of heads and $o_n$ odd amounts.

After one more toss,

$$e_{n+1}=e_n+o_n,\\o_{n+1}=e_n+o_n$$

because an even number can remain even or become odd, and conversely an odd number can become even or stay odd.

As $e_1=o_1=1$, $$e_n=o_n=2^{n-1}.$$

[Using your notation, $a_n=e_{n+1}=o_{n+1}=a_{n-1}+a_{n-1}=2^n$.]