Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.