Solve the following recurrence equation exactly:

Question

Solve the following recurrence equation exactly:

$$T(1) = a, T(2) = b$$ $$T(n) = T(n–2) + c$$

I'm not sure what this is asking, can someone provide some insight?

Answer 1

It means that you are to find a function $f(n,a,b,c)$ such that $T(n) = f(n,a,b,c)$. This article on wiki has several techniques that will help you to find this solution.

Answer 2

If we take one case as $n$ is an even number, then let $n=2k$.

$$\begin{align} T(n) = T(2k) =& T(2k-2)+c\\ =& [T(2k-2-2) + c] + c\\ =& \{[T(2k-2-2-2) + c] + c\}+c\\ =& T(2k-3\times2) + 3c\\ =& T(2k-h\times2) + hc &\text{by induction}\\ \end{align}$$

Now, if you take an appropriate $h$ such that $T(2k-2h$) is a known value, then you can find a close form for $T(n)$, for even $n$.

The other case is similar.

Answer 3

$T(n)$ is in form of $dn + e<br/>$

$$T(1) = a = d + e$$ $$T(2) = b = 2d + e$$ $$d = b - a$$ $$T(n+1) = dn + d + 2 = T(n-1) +c = dn - d + e + c$$ $$2d = c$$ $2a - b = e$$ $$T(3) = 3d + e = T(1) + c = a + c$ $$T(4) = 4d + e = T(2) + c = b + c$$ $$T(n) = nd + e = n(b-a) + 2a - b$$