Prove T(n)= T(n-2)+k is O(n) for all n >1

Question

I'm stuck on trying to prove that

$ T(n)= T(n-2)+k$ is bounded by $O(n)$ for all $n >1$

I expanded it out to reach the following guess: $T(n) = ((n-2)/2)k $

though when I try to prove inductively, I get:

Base case : $T(2) = 0$

which is obviously incorrect. Any help would be greatly appreciated.

Answer 1

The is no relation between $T(m), T(n)$ for $m$ even and $n$ odd.

For $m = 1, 2, \cdots$, we have $T(2m - 1) =T(1) + k(m - 1) , T(2m)=T(2)+k(m-1)$.

Explicitly, for $K > \max\{T(1),T(2)/2,k/2\}$, we have $$T(x)<Kx$$, because $$T(x)=T(2m-1)=T(1)+k(m-1)<K+2K(m-1)=K(2m-1)=Kx$$ and $$T(x)=T(2m)=T(2)+k(m-1)<2K+2K(m-1)=K(2m)=Kx$$.

Answer 2

Actually, you need an initial value for $n=0$ and $n=1$, if you want to find the explicit formula for $T(n)$. Since you're asked to prove the solution is bounded, you may express the formula based on value of $T(0)$ and $T(1)$, and consider them as constants.

Anyway, if I'm not making a mistake $T(n) = T(0) + \dfrac{n}{2}k$ if $n$ is even and $T(n) =T(1) + \left \lfloor \dfrac{n}{2} \right \rfloor k$ if $n$ is odd. Then it is not difficult to check that the solution is $O(n)$.