Solve recurrence relation $T(n-2)+2n$
Solution 1:
What about \begin{align}T(n)&=T(n-2)+2n \\ &= T(n-4)+2n+2(n-2) \\ &=T(n-6)+2n+2(n-2)+2(n-4) \\ &= \dots \\ &=T(n-n)+2n+2(n-2)+2(n-4)+\dots+2(n-(n-2)) \\ &=T(0)+2\sum_{k=0}^{n/2} (n-2k) \\ &= T(0) + n(n/2+1)\end{align} if $n$ is even. Similarly if $n$ is odd.