Simple recursive equation sub-solution: $T(n) = (n+2) + \sum^{n-1}_{i=0}T(i)\\ T(0) = 1$

Question

I have tried to solve a very simple recursive equation:))), but I don't know what's wrong with my brain but I got other solution when I partially solve the equation.

Equation: $$T(n) = (n+2) + \sum^{n-1}_{i=0}T(i)\\ T(0) = 1$$

What I've tried:

$T(n) = (n+2) + \sum^{n-1}_{i=0}T(i)$

$T(n-1) = (n+1) + \sum^{n-2}_{i=0}T(i)$

--------------------------------------------(-)

$T(n) - T(n-1) = (n+2) - (n + 1) + \sum^{n-1}_{i=0}T(i) - \sum^{n-2}_{i=0}T(i)$

T(n) = 1 + 2 * T(n-1)

Bit I think this is wrong, because If I put in 1 to the original equation I got 4 but If I put 1 to the last equation I got 3. Or if I try with 2,3,4,5 I got other values.

I know that this is very easy stupid bug somewhere, tomorrow I will go to the brain medic:)))).

Answer 1

Your solution is correct, but only for $n \geq 2$. Note that in your derivation of the formula $T(n) = 1 + 2T(n-1)$ you are using the expansion $T(n-1) = (n+1) + \sum_{i=0}^{n-2}T(i)$. But for $n=1$ this expansion doesn't hold as $T(n-1) = T(0)$ doesn't have an expansion of this form, it is defined to be 1. So your general solution will be

$$T(n) = \begin{cases} 1 &\mbox{if } n = 0 \\ 4 &\mbox{if } n = 1 \\ 1+ 2T(n-1) & \mbox{if } n \geq 1. \end{cases} $$

Answer 2

You cannot use the formula for $T(n)$ to compute $T(0)$ - try it and see what goes wrong - but this is what you have tried to do when you say $T(1)=1+2*T(0)$.

You need to calculate $T(1)$ by hand, and then you can use the recurrence for $T(n)$ which is valid for $n \gt 1$