MHB How can I solve a recurrence equation of the form T(n) = aT(n-1) + bn?

[DanSlevin]

I have a recurrence equation of the form T(n) = aT(n - 1) + bn where T(1) = 1. In trying to solve this equation, I have tried a top-down and bottom-up approach of "unrolling the equation" but found that I am still having trouble and am unable to solve. Any advice would be appreciated.

 

[Also sprach Zarathustra]

I have a recurrence equation of the form T(n) = aT(n - 1) + bn where T(1) = 1. In trying to solve this equation, I have tried a top-down and bottom-up approach of "unrolling the equation" but found that I am still having trouble and am unable to solve. Any advice would be appreciated.

Let $f(x)$ be generating function of $T_n$:

$$ f(x)=T_0+T_1x+T_2x^2+...$$Hence, we have:

$$ f(x)=\sum_{i=0}^{\infty}T_ix^i=1+ \sum_{i=2}^{\infty}T_ix^i=1+\sum_{i=2}^{\infty}(aT_{i - 1} + bn)x^i $$

$$=1+\sum_{i=2}^{\infty}aT_{i - 1}x^i+ \sum_{i=2}^{\infty}bix^i= 1+a\sum_{i=2}^{\infty}T_{i - 1}x^i+ bx\sum_{i=2}^{\infty}ix^{i-1}$$

$$ =1+a(f(x)-1)+\frac{bx}{(1-x)^2-1} $$So,

$$ f(x)=1+a(f(x)-1)+\frac{bx}{(1-x)^2-1} $$

or:

$$ f(x)=1+\frac{bx}{1-a}\frac{1}{(1-x)^2-1}$$Now, all you need is find the coefficient of $x^n$ in the above.

 

[DanSlevin]

I believe I mistook your "...thinking." remark as telling me to just think. I'm sorry and thank you for time.

 

[Also sprach Zarathustra]

I believe I mistook your "...thinking." remark as telling me to just think. I'm sorry and thank you for time.

It's ok. :)There is few mistakes in my post, I will try to fix them, but this is one way to the right answer...

 

[HallsofIvy]

A linear recurrance is a lot like a linear differerential equation- we can find the general solution to the associated "homogeneous" equation and a solution to the entire equation and add to get the general solution to the entire equation.

Here, the associated homogeneous equation is just T(n)= aT(n-1). If T(0)= C, T(1)= Ca, T(2)= (Ca)a= Ca^2, etc. In other words the general solution to the associated Homogeneous equation is T(n)= Ca^n. Now we need just a single solution to T(n)= aT(n-1)+ bn. If T(0)= 0, T(1)= aT(0)+ b= b, T(2)= aT(1)+ b= ab+ b, T(3)= aT(2)+ b= a^2b+ ab= (a^2+ a)b, T(4)= aT(3)+ b= (a^3+ a^2)b+ b= (a^3+ a^2+ a)b. See the pattern? T(n)= (a^(n-1)+ a^(n-2)+ ...+ a^2+ a)b.

Putting those together T(n)= Ca^n+ b(a^(n-1)+ a^(n-2)+ ...+ a^2+ a)

T(1)= 1 then becomes Ca+ b= 1 so that C= (1-b)/a.

 

[DanSlevin]

A linear recurrance is a lot like a linear differerential equation- we can find the general solution to the associated "homogeneous" equation and a solution to the entire equation and add to get the general solution to the entire equation.

Here, the associated homogeneous equation is just T(n)= aT(n-1). If T(0)= C, T(1)= Ca, T(2)= (Ca)a= Ca^2, etc. In other words the general solution to the associated Homogeneous equation is T(n)= Ca^n. Now we need just a single solution to T(n)= aT(n-1)+ bn. If T(0)= 0, T(1)= aT(0)+ b= b, T(2)= aT(1)+ b= ab+ b, T(3)= aT(2)+ b= a^2b+ ab= (a^2+ a)b, T(4)= aT(3)+ b= (a^3+ a^2)b+ b= (a^3+ a^2+ a)b. See the pattern? T(n)= (a^(n-1)+ a^(n-2)+ ...+ a^2+ a)b.

Putting those together T(n)= Ca^n+ b(a^(n-1)+ a^(n-2)+ ...+ a^2+ a)

T(1)= 1 then becomes Ca+ b= 1 so that C= (1-b)/a.

Thank you for your reply. I'm a little confused with the part with T(3)= aT(2)+ b, shouldn't this be T(3)= aT(2)+ bn? I'm confused as to where the n went that was on the end.

 

[chisigma]

I have a recurrence equation of the form T(n) = aT(n - 1) + bn where T(1) = 1. In trying to solve this equation, I have tried a top-down and bottom-up approach of "unrolling the equation" but found that I am still having trouble and am unable to solve. Any advice would be appreciated.

Let's write the recurrence relation in a slight different form...

$y_{n+1}= x\ y_{n} + c_{n+1}\ ,\ y_{0}=c_{0}$ (1)

In the 'tutorial posts' about difference equation I wrote for MHF this case was specifically examined and the solution is given by...

$y_{n}= c_{0}\ x^{n} + c_{1}\ x^{n-1} +...+ c_{n-1}\ x + c_{n}$ (1)

... and it is easy to see that (1) is a polynomial. This procedure allows to compute a polynomial of order n with a minimum number of operations [n sums and n multiplications...] and it is known as "Horner method for computing polynomials'...

Kind regards

$\chi$ $\sigma$

 

[HallsofIvy]

Thank you for your reply. I'm a little confused with the part with T(3)= aT(2)+ b, shouldn't this be T(3)= aT(2)+ bn? I'm confused as to where the n went that was on the end.

Oh, bother! Yes, you are right I completely missed the "n" there!

If we take T(0)= 0, T(1)= aT(0)+ b(1)=b. T(2)= aT(0)+ b(2)= ab+ 2b= (a+2)b. T(3)= aT(2)+ b(3)= (a^2+ 2a+ 3)b. T(4)= aT(3)+ b(4)= (a^3+ 2a^2+ 3a+ 4)b. T(5)= aT(4)+ 5b= (a^4+ 2a^3+ 3a^3+ 4a+ 5)b. Now, we are getting a different pattern but yet a pattern.