# solving the recurrence t(n)=t(n-2)+d*(n^2)/2 with iteration method

How can I solve $$T(n)=T(n-2)+\frac {d}{2}n^2$$ I couldnt find $$d$$ (dont know if I have to) and after 3 iterations I got to $$k= \frac{n-1}{2}$$ but had trouble to continue.

• You've misunderstood the question. You're not supposed to be finding $d$: it's just some constant whose numerical value doesn't matter. Consider the simpler question, "If $x=d+3$, what is $x^2$?" There, you're just supposed to say that $x^2=(d+3)^2=d^2+6d+9$ -- you're not being asked to solve for $d$ and say "$d=\dots$". Here, you're being asked to express $T(n)$ as a function of $n$ and $d$ that doesn't involve $T$ -- the answer will be something like "$T(n) = dn^3$" (but not literally that; I didn't try to work it out). You say "$k=(n-1)/2$" but what is $k$? There's no $k$ in the question. – David Richerby Jun 5 '19 at 13:57

This answer assumes that $$T(1) = \frac{d}{2}$$

Your recurrence relation, in closed form, would be:

\begin{align} T(n) & = \frac{d}{2} n^2 + \frac{d}{2} (n-2)^2 + \frac{d}{2} (n-4)^2 + \dots + \frac{d}{2}\\ & = \sum_{i=0}^\frac{n-1}{2} \frac{d}{2}(n-2i)^2\\ \end{align}

Which, with little effort, can be simplified further:

$$\dots = \frac{d}{2} \sum_{i=0}^\frac{n-1}{2}n^2-4ni+4i^2 = \frac{dn^2}{4}(n-1) -2dn\sum_{i=0}^\frac{n-1}{2}i +2d\sum_{i=0}^\frac{n-1}{2}i^2$$

For further simplification, you can use the facts that:

$$\sum_{i=1}^n i=\frac{n(n+1)}{2}$$

$$\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$$

But I'll leave that to you.