What is the closed form for the general recurrence relation?

Question

$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.

Answer 1

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.