# Series, proving the $n$-th element

I'm trying to show that the relationship between two successive elements in the series $$1, 2, 4, 8...$$ can be described a $a_{n} = a_{n-1} + a_{n-1}$.

I'm interested in the number of combinations that give an even amount of tails when a coin is flipped $n$ times.

If I flip a coin $1$ time, it's either going to be heads or tails. So I have $1$ combination where the amount of tails is even (which is when I get heads because $0$ is even).

For $2$ flips I have $2$ combinations which matches an even amount of tails:

HH, HT, TH, TT

And for 3 flips I have $4$ combinations which gives me an even amount of tails:

HHH, HHT, HTH, THH, TTH, THT, HTT, TTT

This series takes the shape of $1, 2, 4, 8, 16...$ and so on, where each element is the previous element multiplied by $2$.

What I'm trying to do is simply put words on why this relationship works the way it does. In other words, how can I be $100\%$ sure that there are twice as many combinations with an even amount of tails for 100 flips when compared to $99$ flips.

Help is appreciated!

Well, you have the right idea : for $n$ flips, there are $2^n$ combinations.

For instance, for 3 flips you get HHH, HHT, HTH, THH, TTH, THT, HTT, TTT - that is $2^3 = 8$.

In your case, you only want those who gives you an even number of tails, which is half the previous number : $\frac{2^3}{2} = 2² = 4$, because the distribution is homogenous. Indeed, there is 50% chance of getting tails, and 50% chance of getting heads when you toss the coin, assuming it is perfectly balanced, no one cheats, etc.

So, you have a geometric progression that goes like this : $$a_{n+1} = 2a_n$$ with $a_0 = 0$. (if you flip 0 times the coin, well...)

When you flip a coin $n$ times, each flip can have two outcomes - $H$ or $T$. Since each flip is independent of the rest, the number of outcomes possible are $$2\times2\times\cdots\times2=2^n$$

Now, exactly half of these outcomes must have an even number of tails. This can be understood as follows.

For the first flip, you can get a $H$ or a $T$ with equal probability. Clearly, half ($1$) of the number of possible outcomes ($2$) have an even number of tails.

Suppose after the $k^{th}$ flip, you have exactly half of outcomes with an even number of tails.

For the $(k+1)^{th}$ flip, there is an equal probability of getting a $H$ or a $T$. Thus, for every outcome, we would get two outcomes, each corresponding to an even and odd number of tails. Hence, the number of outcomes having an even number of tails after the $(k+1)^{th}$ flip will be half the total number of outcomes.

So, using mathematical induction, we can say that after $n$ flips, the number of outcomes having an even number of tails will be $$\frac{2^n}2=2^{n-1}$$

Now, if $$a_n=2^{n-1}$$ It is clear that $$a_{n+1}=2^n=2.2^{n-1}=2^{n-1}+2^{n-1}=a_n+a_n$$

• how exactly did you get that $a_{n+1} = 2^n$ ? Feb 18, 2016 at 18:00
• @user3067688 $a_n=2^{n-1}$. Replace $n$ with $n+1$. You get $a_{n+1}=2^n$ Feb 18, 2016 at 18:04
• Okay thanks, could you elaborate a little bit more on this part? "Hence, the number of outcomes having an even number of tails after the (k+1)th(k+1)th flip will be half the total number of outcomes." There are 4 cases right? Feb 18, 2016 at 18:48
• @user3067688 Yes, there are four cases. After the $k^{th}$ flip, supposing the hypothesis is true, we have $2^{k-1}$ outcomes with an even number of tails, and $2^{k-1}$ outcomes with an odd number of tails. For each of these $2^k$ outcomes, we get $2$ outcomes after the $k^{th}$ flip. From the first set of $2^{k-1}$ outcomes, now exactly half will have an even number of tails, i.e., $2^{k-2}$. Likewise for the second set. Thus, the total number of outcomes after the $(k+1)^{th}$ flip will be $2.2^{k-2}=2^{k-1}$ Feb 18, 2016 at 19:04