# What is the closed form for the general recurrence relation?

$T(N) = a\cdot T(N-b) + c \cdot N + d$

$T(0) = 0$

I honestly don't understand this concept at all. Any help would be great.

-
This problem is not well-posed; $T(N)$ relies only on $T(N-b)$ and you've only specified $T(0)$. For instance, suppose $b = 2$; then $T(2)$ is determined, but $T(1)$ is not. Is there a typo? – A Blumenthal Jan 31 '13 at 20:35
there may be several cases, depending on the values of a, b, and c. N is assumed to be a variable of b. – John Jan 31 '13 at 20:43

## 1 Answer

We usually write such relations as follows:

$$T_n - a T_{n-b} = c n + d$$

with initial condition:

$$T_0 = 0$$

where at least $n \ge 0$ and $b$ are integers. In this case, your initial condition is only sufficient to specify a unique solution when $|b| = 1$.

A recurrence like this is what we call inhomogeoneous because the right hand side is nonzero. In this case, the solution has two pieces: a homogeneous part and an inhomogeneous part. The homogeneous part satisfies

$$T_n^{(H)} - a T_{n-b}^{(H)} = 0$$

with $T_n^{(H)}$ satisfying the specified initial conditions. In this case, assume $b=1$. We find in this case that

$$T_n^{(H)} = R a^n$$

for some constant $R$. I'll come back to this.

To find this inhomogeneous piece $T_n^{(I)}$, one way to proceed is to look at the right-hand side and guess. In this case, we might guess that $T_n^{(I)} = p n+q$, and solve for $p$ and $q$. Doing this, we see that

$$T_n^{(I)} - a T_{n-1}^{(I)} = (p n+q) - a (p (n-1)+q) = p (1-a) + q (1-a + a p) = c n + d$$

We may now solve for the unknowns $p$ and $q$ in terms of the knowns $a$, $c$, and $d$:

$$p (1-a) = c$$ $$q (1-a + a p) = d$$

from which we get that

$$T_n^{(I)} = \frac{c}{1-a} n + \frac{(1-a) d}{(1-a)^2 + a c}$$

and our general solution is

$$T_n = R a^n + \frac{c}{1-a} n + \frac{(1-a) d}{(1-a)^2 + a c}$$

Now go back to our initial condition: $T_0 = 0$. This means that

$$R + \frac{(1-a) d}{(1-a)^2 + a c} = 0$$

which determines $R$, and $T_n$, uniquely. I hope this helps some.

-
Thank you for taking the time to write all this out. This does help answer my question. I appreciate it. – John Jan 31 '13 at 20:50
My pleasure, anytime. – Ron Gordon Jan 31 '13 at 20:52
+1 for thoroughness. – Rick Decker Feb 1 '13 at 1:59