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

4 Answers 4

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

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

$\endgroup$
0
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.$$

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

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

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.