Prove that a number $n$ can be represented in $2^{n-1}$ ways of summation... The question as just as the title reads-

Prove that a number $n$ can be represented in $2^{n-1}$ ways of summation

We know that-

$1=1+0$ So,it can be represented in $1$ way of sum as indicated by the form $2^{n-1}=2^0=1$
Similarly,$3$ can be represented in $1+1+1$ or $2+1$ or $1+2$ or $3+0$ .So,total $4$ ways as indicated by the formula $2^{3-1}=2^2=4.$

So,I need to prove that any number $n$ can be expressed in $2^{n-1}$ ways for summation.
I need some help to start on the problem.
Thanks for any response!!
 A: Consider the following string
$$(1 \ 1 \ \cdots \ 1)$$
made of $n$ ciphers $1$. Between any two consecutive ciphers, you can choose to put the symbol "$+$" or the symbol "$)+($". Since you have to make $n-1$ choices between two symbols, you have a total of $2^{n-1}$ possibilities.
As an example:
$$5=3+2$$
corresponds to
$$5=(1 \ + \ 1 \ + \ 1 \ )+( \ 1 \ + \ 1)$$
and in this case we have chosen the sequence of symbols $+,+, )+( , +$
A: Given any general $n$, look at the number of ways to represent $n$ as the sum of $1$ positive integer, sum of $2$ positive integers, $\dots$, sum of $n$ positive integers.
Now, we know that the number of positive integer solutions to
$$x_1+x_2+\dots x_r=n$$
is given by
$$X_r=\binom{n-1}{r-1}$$
So, to find the number of ways of expressing $n$ as a sum, you only need to find
$$\sum_{r=1}^n X_r = \sum_{r=1}^n \binom{n-1}{r-1} = 2^{n-1}$$
There are two ways to prove the final statement

*

*Proof by WolframAlpha


*Proof by strong induction where in the induction step you simply need to repeatedly use the formula $\binom{n}{r}+\binom{n}{r-1}=\binom{n+1}{r}$.
I'll leave it to you to decide upon which method to use for the proof :)
