Solving Recurrence Relation with substitution

Question

How to solve T(n) = T(n-2) + n using iterative substitution

Base case:
T(0) = 1
T(1) = 1

Solve:
T(n) = T(n-2) + n

Currently I have:

T(n) = T(n-2) + n
     = T(n-4) + n - 2 + n = T(n-4) + 2n - 2
     = T(n-6) + n - 4 + n - 2 + n = T(n-6) + 3n - 6
     = T(n-8) + n - 6 + n - 4 + n -2 + n = T(n-8) + 4n - 12
     = T(n-10) + n - 8 + n - 6 + n - 4 + n - 2 + n = T(n-10) + 5n - 20

The pattern I see is:

$$\ T(n-2 \sum_{i=1}^k i) + n \sum_{i=0}^k i - \sum_{i=0}^{k-1} i(i+1) $$

but this may be wrong because I am completely stuck after this

Answer 1

$$\begin{align} T(n) &= T(n-2) + n \\ T(n) &= T(n-4) + (n-2) + (n-0) \\ T(n) &= T(n-6) + (n-4) + (n-2) + (n-0) \\ T(n) &= T(n-8) + (n-6) + (n-4) + (n-2) + (n-0) \\ \vdots\\ T(n) &= T(n-2r) + \sum_{k=0}^{r-1}(n-2k)\\ T(n) &= T(n-2r) + \left(n\sum_{k=0}^{r-1}(1)\right)-2\left(\sum_{k=0}^{r-1}k\right)\\ T(n) &= T(n-2r) + nr-2\dfrac{r(r-1)}{2}\\ T(n) &= T(n-2r) + nr - r^2 + r \\ \end{align}$$

We know that $T(0) = T(1) = 1$, so we need to set $n-2r = 0$ or $1$ in order for $T(n-2r) = 1$ to be reached, which is achieved when $r = \left\lfloor\dfrac{n}{2}\right\rfloor$ where $\left\lfloor x\right\rfloor$ is the floor function of $x$.

Therefore:

$$T(n) = 1 + n\left\lfloor\dfrac{n}{2}\right\rfloor - \left\lfloor\dfrac{n}{2}\right\rfloor^2 + \left\lfloor\dfrac{n}{2}\right\rfloor$$

Answer 2

If $n$ is even,

$$\sum_{k=1}^{\frac{n}{2}}[T(2k)-T(2k-2)]=\sum_{k=1}^{\frac{n}{2}}2k$$

$$T(n)-T(0)=\frac{1}{2}\left(\frac{n}{2}\right)(2+n)$$

$$T(n)=\frac{1}{4}n^2+\frac{1}{2}n+1$$

If $n$ is odd,

$$\sum_{k=1}^{\frac{n-1}{2}}[T(2k+1)-T(2k-1)]=\sum_{k=1}^{\frac{n-1}{2}}(2k+1)$$

$$T(n)-T(1)=\frac{1}{2}\left(\frac{n-1}{2}\right)(3+n)$$

$$T(n)=\frac{1}{4}n^2+\frac{1}{2}n+\frac{1}{4}$$