0
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you please explain how does it give $T(n)= -2n -3$? $\endgroup$ – Matjag May 30 at 16:07
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.