2^2n
3^n
2^n
2^(n-2)

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

The standard proof is as follows. For a given positive integer $n$ , write out a string of $n 1$ 's with small circles between the $1$ 's as follows:

$1 o 1 o 1 o 1.... 1 o 1 o 1$ .

Since there are $n 1$ 's there will be $n - 1$ small circles. We then replace a combination of the circles with $+$ signs to create a particular composition of the integer $n$ .

So, for example, with $n = 3$ , we start with $1 o 1 o 1$ . By replacing only the first circle with a $+$ sign we create the composition $1 + 2$ , and by replacing only the second circle with a $+$ sign we create the composition $2 + 1$ . Replacing both circles gives us $1 + 1 + 1$ , and replacing neither gives us the composition $3$ .

In this way, for any $n$ , we can create a one-to-one correspondence between the sequences as described in the above process and the distinct compositions of $n$ . Since we have $n - 1$ circles we can potentially convert to $+$ signs we have $2^{n-1}$ such sequences, indicating that $a = 2^{n-1}$ , and thus $2a = \boxed{2^n}$ .