<s>[INST] Solving Recurrence Relation with substitution 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
 [/INST] $$\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$$
</s>