# Find a generating function and a closed form for the sequence $c_{n+1} = \sum_{i=0}^{n}c_i$

Consider the recurrence given by $c_0 = 1$, $c_{n+1} = \sum_{i=0}^{n}c_i$ for $(n \ge 0)$. Find a generating function and a closed form for the sequence. Hint: consider $\frac{C(x)}{(1-x)}$.

My attempt:

$\frac{C(x)}{(1-x)} = c(x)(1 + x + x^2 + x^3 + ... )$ How does this help?

I see the similarities to Segner's recurrence relation and Catalan Recurrence, but the removal of $c_{n-i}$ has me lost. I tried calculating the first few iterations:

$c_1 = c_0 = 1$

$c_2 = c_0 + c_1 = 1 + 1 = 2$

$c_3 = c_0 + c_1 + c_2 = 1 + 1 + 2 = 4$

$c_4 = c_0 + c_1 + c_2 + c_3 = 1 + 1 + 2 + 4 = 8$

but that's as far as I can get.

• Your first few iterations are wrong. When calculating $c_3$, $c_2 = 2$. After you fix that, notice that the $c_i$ are just powers of $2$. – Mike Pierce Nov 5 '17 at 3:57

You can write for $n\geq 2$ \begin{align*} c_{n+1}=\sum_{i=0}^nc_i=c_n+\sum_{i=0}^{n-1}c_i=2c_n \end{align*} In particular, you get $c_{n+1}=2^nc_1=2^{n}$.
Translating the recurrence into a generating function we get that $$\frac{C(x)-1}{x}=\frac{C(x)}{1-x}$$ and upon solving for C(x) we get that $$C(x)=\frac{x-1}{2x-1}=\frac{1-x}{1-2x}=\sum_{n=0}^{\infty}2^nx^n-\sum_{n=1}^{\infty}2^{n-1}x^n.$$ Hence $$C_n=2^n-2^{n-1}=2^{n-1};\quad (n\geq 1).$$