Generating Functions with composition For a nonnegative integer $n$, a composition of $n$ means a partition in which the order of the parts matters.
Consider the generating function
$$C(x) = \sum_{n=0}^{\infty} c_nx^n,$$
where $c_n$ is the number of distinct compositions of $n$ (note that $c_0=1$ by convention).
What is the value of $C\left(\tfrac 15\right)$?

How can I start this?
 A: Hint: $c_n = 2^{n-1}$ for $n>0$.
A: Think about $$(x+x^2+x^3+\cdots)(x+x^2+x^3+\cdots)\cdots\underbrace{(x+x^2+x^3+\cdots)}_{m-\text{th term}}$$
Coefficient of $x$ in the above expression is the number of ways we can add up $m$ natural numbers to $n$ respecting the order.
So the generating function is 
$$1+\sum_{m=1}^\infty(x+x^2+x^3+\cdots)^m=\sum_{m=0}^\infty\left({x\over1-x}\right)^m={1-x\over1-2x}\\=(1-x)\sum_{m=0}^\infty(2x)^m\\
\therefore c_n=2^n-2^{n-1}=2^{n-1}$$
A: You can construct the partitions in a systematic way: take the partitions of $n-1$, and form two new sets: in blue, by appending $1$, in green by adding $1$ to the last element.
$$1\to(1)$$
$$2\to(1,1),(2)$$
$$3\to(1,1,1),(2,1),(1,2),(3)$$
$$4\to(1,1,1,\color{blue}1),(2,1,\color{blue}1),(1,2,\color{blue}1),(3,\color{blue}1)(1,1,\color{green}2),(2,\color{green}2),(1,\color{green}3),(\color{green}4)$$
The partitions so obtained are all different and they exhaust the partitions of $n$ (you find all the partitions of $n$ ending in $1$ and all the partitions of $n$ not ending in $1$, which must be partitions of $n-1$ when you deduce $1$). This establishes the recurrence
$$c_n=2c_{n-1}$$
and, for $n>0$,
$$c_n=2^{n-1}.$$
Then,
$$1+\frac12\sum_{n=1}^\infty\left(\frac25\right)^n.$$
