I am trying to figure out how to find the Asymptotic bounds for $T(n)=T(n-2)+n$ and I am pretty sure that I need to use the substitution method. I have what I believe is a proof using the Subtract and Conquer method, which was not a method that has been covered yet.
Subtract and Conquer
$T(n)=T(n-2)+n$
Subtract and Conquer: $T(n) = aT(n-b) + f(n)$ when $n > 1$
$T(n) = [O(n^k),\ if\ a < 1\ |\ O(n^{k+1}),\ if\ a = 1\ |\ O(n^{ka^{n/b}}),\ if\ a >1]$
$a = 1,\ b = 2,\ k = 1$
$T(n) = O(n^{1+1})$
$\equiv T(n) = \mathcal{O}(n^2)\ \blacksquare$
I tried to formulate one by expanding the recurrence, but I just don't know where to go after doing so
$T(n)=T(n-2)+n$
$T(n-2) = [T(n-4)+(n-2)]+n$
$ = T(n-4)+2n-2$
$T(n-4) = [T(n-6)+(n-4)]+2n-2$
$=T(n-6)+3n-6$
$T(n-6) = [T(n-8)+(n-6)+3n-6$
$=T(n-8)+4n-12$
Substitute k: $\ T(n-2k)+kn-c_1$
And then with the substitution method:
$T(n)=T(n-2)+n$
Assume: $\ T(1) = \Theta(1)$
Guess: $O(n^2)$
Assume: $\ T(k) \leq c \cdot k^2\ $ for $k<n$
$ \leq c(n-2)^2+n$
$ = cn^2+(-4)+n$
$ = cn^2-(4-n)\ $
$ (4-n) \geq 0\ for\ n\geq4$
$ T(n) = O(n^2)\ \blacksquare$
I'm not even sure if I'm in the ballpark here. If someone has a good article to read or some advice I would really appreciate it.
For even $n=2k$,
$$T(2k)=T(2(k-1))+2k$$ or $$T'(k)=T'(k-1)+2k$$ which is a simple first order recurrence on $k$ (sum of integers), and
$$T(n)=T(2k)=2\frac{k(k+1)}2+T_0=\frac n2(\frac n2+1)+T_0.$$
For odd $n=2k+1$,
$$T(2k+1)=T(2(k-1)+1)+2k+1$$ or $$T'(k)=T'(k-1)+2k+1$$ which is a simple first order recurrence on $k$ (sum of odd integers), and
$$T(n)=T(2k+1)=k(k+2)+T_1=\frac{(n-1)(n+3)}4+T_1.$$
Hence whatever the initial values, $T(n)=\Theta(n^2)$ and $\lim_{n\to\infty}\dfrac{T(n)}{n^2}=\dfrac14$.