Solve recurrence relation $T(n-2)+2n$

Question

Prove: $T(n) = T(n-2)+2n$ is $O(n^2)$.

I'm trying to solve by substitution method, what I reached so far is:

$T(n-2)+2n$ = $T(n-4)+4n - 4$ = $T(n-6)+6n - 12$ = $T(n-8)+ 8n - 24$

How do I generalize this?

Answer 1

What about \begin{align}T(n)&=T(n-2)+2n \\ &= T(n-4)+2n+2(n-2) \\ &=T(n-6)+2n+2(n-2)+2(n-4) \\ &= \dots \\ &=T(n-n)+2n+2(n-2)+2(n-4)+\dots+2(n-(n-2)) \\ &=T(0)+2\sum_{k=0}^{n/2} (n-2k) \\ &= T(0) + n(n/2+1)\end{align} if $n$ is even. Similarly if $n$ is odd.

Answer 2

Note that if $T(0)=a,\;T(1)=b$, then for $n\in\mathbb N$ $$T(2n-1)=b-2+2n^2$$

$$T(2n)=a+2n\cdot(n+1)$$

Answer 3

You have $T(n)-T(n-2)=2n$

Solve first homogeneous equation $T(n)-T(n-2)=0$

It depends of $T(0)$ and $T(1)$ such that $\begin{cases}T(2n)=T(0)\\T(2n+1)=T(1)\end{cases}$

We can also solve the characteristic equation $r^2-1=0$ with root $\pm 1$ to say $T(n)=a\times 1^n+b\times(-1)^n$

Anyway we can combine both into $$T(n)=a+b(-1)^n=\frac{T(0)+T(1)}2+(-1)^n\frac{T(0)-T(1)}2$$

Now let's find a particular solution to the complete equation. Since RHS = $2n\times 1^n$ where $1$ is a root of characteristic equation we need to find a polynomial with a degree $+1$ compared to $\deg(2n)$.

So we search for $An^2+Bn+C$.

$\require{cancel}\cancel{An^2+Bn+C}-A(\cancel{n}-2)^2-B(\cancel{n}-2)-\cancel{C}=2n\iff 4An-4A+2B=2n$

We get $A=\frac 12$ and $2B-4A=2B-2=0\iff B=1$ and solution is $\dfrac{n(n+2)}2+C$

In the end, the general solution is

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

At infinity $\boxed{T(n)\sim \frac 12 n^2}$

---

Of course if you are only interested in showing $T(n)=O(n^2)$ then you can skip much of the calculation details.

Just go for characteristic equation $r^2-1=0$ so roots are $\pm 1$

So particular solution in of degree = $deg(2n)+1=2$

Thus $T(n)=a+b(-1)^n+(cn^2+dn+e)=O(n^2)$ at infinity.

Without any need for expliciting $a,b,c,d,e$.