<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] 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}$$
</s>