# Solving recursive formula including a sum

I have the following formula $$T(1) = 1$$ $$T(n) = \sum_{i=1}^{n-1}T(i) + n^2$$

And I have to find an iterative form of any $$T(n)$$ for $$n>1$$

One thing I have managed to accomplish so far is calculating $$T(n+1) = 2T(n) + 2n + 1$$ but I don't really know where to go from there.

I'm really new to recursion in mathematics and all the methods seem to either include guessing or require a lot of hardcore algebra. Any help will be much appreciated.

• By *, do you mean $\times$, $+$ or what? Because your recursion relation suggests it can't be $\times$. – J.G. May 30 at 14:29
• That was a typo, sorry, and thank you for pointing out. – Matjag May 30 at 14:32
• You could continue by, say, noting that $T(n)=2T(n-1)+2(n-1)+1$ and subtract to remove the $n$ term. Then you can do it again to kill the constant. – lulu May 30 at 14:41

hint

$$2^{n-2}T(2)=2^{n-1}T(1)+2^{n-2}.3$$ $$2^{n-3}T(3)=2^{n-2}T(2)+2^{n-3}.5$$ •••

$$2^2T(n-2)=2^3T(n-3)+2^2(2n-5)$$ $$2T(n-1)=2^2T(n-2)+2(2n-3)$$ $$T(n)=2T(n-1)+(2n-1)$$

Define $$A(n):=T(n)-an-b$$, where we'll choose $$a,\,b$$ to simplify the recursion relation$$A(n+1):=2A(n)+(a+2)n+b-a+1.$$With $$a=-2,\,b=-3$$, we have$$A(1)=6,\,A(n+1)=2A(n)\implies A(n)=3\cdot2^n,\,T(n)=3\cdot2^n-2n-3.$$

Actually, $$T(n+1) = 2T(n) + 2n + 1$$ is the decisive step to solving this problem: an ansatz $$T(n)=an+b$$ gives immediately $$T(n)=-2n-3,$$ and the difference of this particular solution to the actual one must be a solution of the homogeneous equation $$T(n+1)=2T(n),$$ i.e. $$T(n)=c\cdot2^n$$. From $$T(1)=1,$$ we get $$c=3$$, so $$T(n)=3\cdot2^n-2n-3.$$

• Could you please explain how does it give $T(n)= -2n -3$? – Matjag May 30 at 16:07

Let $$S(n)=\sum_{i=1}^n T(n)$$. This allows you to rewrite the recurrence as

$$S(n)-S(n-1)=S(n-1)+n^2,$$ with $$S(2)=1$$.

As the recurrence is linear, we can first solve the homogeneous par of the equation

$$S(n)=2S(n-1)$$ and it is easy to see that

$$S(n)=c\,2^n$$ holds.

Now we have to find a particular solution of the complete equation

$$S(n)-2S(n-1)=n^2.$$ We can infer that if we plug a quadratic polynomial on the left, we will get a quadratic polynomial:

$$n^2=pn^2+qn+r-2(p(n-1)^2+q(n-1)+r)=-pn^2+(4p-q)n+2q-2p-r$$

and by identification we get the solution

$$-n^2-4n-6.$$

Finally, combining and using the initial condition,

$$S(n)=19\cdot2^{n-2}-n^2-4n-6$$

and

$$T(n)=S(n)-S(n-1).$$