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.
On
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.$$
On
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).$$
On
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.$
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)$$