Solving recursion formula with sum

Question

I am trying to solve the following recurrence, but i am stuck...

$$t(n)=n + \sum_{j=1}^n t(n-j)$$

I really appreciate your help,

Tarcísio.

Answer 1

Notice that as $j$ runs from $1$ to $n$ in the summation, $n-j$ runs from $n-1$ down to $0$, so we can rewrite the recurrence as

$$t(n)=n+\sum_{k=0}^{n-1}t(k)\;.\tag{1}$$

It never hurts to gather some numerical data:

$$\begin{align*} t(0)&=0+t(0)\\ t(1)&=1+t(0)\\ t(2)&=3+2t(0)\\ t(3)&=7+4t(0)\\ t(4)&=15+8t(0)\\ t(5)&=31+16t(0) \end{align*}$$

At this point there’s a pretty obvious pattern: it appears that

$$t(n)=2^n-1+2^{n-1}t(0)=2^{n-1}\big(t(0)+2\big)-1\tag{2}$$

for $n>0$. Proving $(2)$ is just a matter of verifying that it gives the correct value for $t=1$ and satisfies the recurrence $(1)$, i.e., that

$$2^n-1+2^{n-1}t(0)=n+\sum_{k=1}^{n-1}\left(2^k-1+2^{k-1}t(0)\right)+t(0)\;,$$

which is a fairly straightforward calculation.

Added: For a completely different approach, note that

$$t(n)-t(n-1)=n+\sum_{k=0}^{n-2}t(k)=1+\left((n-1)+\sum_{k=0}^{n-2}t(k)\right)=1+t(n-1)$$

and hence $$t(n)=1+2t(n-1)$$ for $n\ge 2$. This is a simple recurrence that can be solved in a variety of ways.