0

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.

Matjag
  • 1
  • By *, do you mean $\times$, $+$ or what? Because your recursion relation suggests it can't be $\times$. – J.G. May 30 '20 at 14:29
  • That was a typo, sorry, and thank you for pointing out. – Matjag May 30 '20 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 '20 at 14:41

4 Answers4

1

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

0

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

hamam_Abdallah
  • 62,951
0

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

J.G.
  • 115,835
0

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