Welcome to our community

Be a part of something great, join today!

Proving solution to recurrence equation using induction

ATroelstein

New member
Jun 30, 2012
15
Hello, I have the following recurrence equation

$$T(n)=aT(n-1)+bn$$

Using substitution, I have solved it to the following form

$$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$

Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this proof would be appreciated. Thank you.
 

CaptainBlack

Well-known member
Jan 26, 2012
890
Hello, I have the following recurrence equation

$$T(n)=aT(n-1)+bn$$

Using substitution, I have solved it to the following form

$$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$

Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this proof would be appreciated. Thank you.
First, where did you specify that \(T_1=1\) ?

To prove that \[T_n=a^{n-1}T_1+b\sum_{i=2}^n i \;a^{n-i}\ \ \ ...(1)\] Start by showing that the recurrence holds for \(T_2\). Now plug the general term in \((1)\) above and show that it can be written: \[T_{n+1}=a^{(n+1)-1}T_1+b\sum_{i=2}^{n+1} i \;a^{(n+1)-i}\ \ \ ...(2)\]Then that the base case holds and \((1) \Rightarrow (2)\) together prove by induction that \((1)\) is the solution to your recurrence.

You might find this easier to do if you replace the summation by its sum, but it can be done without this.

CB
 

ATroelstein

New member
Jun 30, 2012
15
Thanks for the explanation. I have a much better understanding of how to conduct the proof now. I have an additional question now though. In order to turn the summation into the sum, what technique should I be using?
 

CaptainBlack

Well-known member
Jan 26, 2012
890
Thanks for the explanation. I have a much better understanding of how to conduct the proof now. I have an additional question now though. In order to turn the summation into the sum, what technique should I be using?
There are a number of approaches, the one I find easiest to remember is:
\[\sum_{k=2}^n k\; a^{n-k}=a^{n-1}\sum_{k=2}^n k\;a^{-k+1}\]

Now we focus on the final summation and put \(x=1/a\), which gives:
\[\sum_{k=2}^n k\;a^{-k+1}=\sum_{k=2}^n k\;x^{k-1}=\left(\sum_{k=1}^n k\;x^{k-1}\right)-x\]
but:
\[\sum_{k=1}^n k\;x^{k-1}=\frac{d}{dx}\sum_{k=0}^n x^k=\frac{d}{dx}\left(\frac{1-x^{n+1}}{1-x}\right)\]

CB
 

checkittwice

Member
Apr 3, 2012
37
Hello, I have the following recurrence equation

$$T(n)=aT(n-1)+bn$$

Using substitution, I have solved it to the following form

$$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$

Now I am trying to prove my solution is correct using > > induction, < <
but I'm a bit lost. Any advice on how to conduct this proof
would be appreciated. Thank you.
CaptainBlack said:
but:
\[\sum_{k=1}^n k\;x^{k-1}=\frac{d}{dx}\sum_{k=0}^n x^k=\frac{d}{dx}\left(\frac{1-x^{n+1}}{1-x}\right)\]

I wouldn't think that any calculus would be used in this intended induction
problem, as induction and summations have been taught in college algebra
and/or pre-calculus courses, but not taking derivatives.
 
Last edited:

CaptainBlack

Well-known member
Jan 26, 2012
890
I wouldn't think that any calculus would be used in this intended induction
problem, as induction and summations have been taught in college algebra
and/or pre-calculus courses, but not taking derivatives.
I did say it was the method that I found esiest to remember not that it was the only method. A non-calculus method follows (probably with errors):

\[\begin{aligned}S_n(x)= \sum_{k=1}^n k\;x^{k-1}&=\left(1+x+x^2+...+n^{n-1} \right)+\left( x+2x^2+...+(n-1)x^{n-1}\right) \\ &=\frac{1-x^n}{1-x}+x \left(1+2x+...+(n-1)x^{n-2} \right)\\ &= \frac{1-x^n}{1-x}+x \left( \sum_{k=1}^n k\;x^{k-1} - nx^{n-1} \right)\\&= \frac{1-x^n}{1-x}+x \left( S_n(x) - nx^{n-1} \right)\end{aligned} \]

Then its just algebra.

CB
 

chisigma

Well-known member
Feb 13, 2012
1,704
Hello, I have the following recurrence equation

$$T(n)=aT(n-1)+bn$$

Using substitution, I have solved it to the following form

$$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$

Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this proof would be appreciated. Thank you.
Let's write the difference equation as...

$\displaystyle T_{n+1}=a\ T_{n} + b\ (n+1)$ (1)

As explained in http://www.mathhelpboards.com/threads/426-Difference-equation-tutorial-draft-of-part-I the solution is given by...

$\displaystyle T_{n}= a^{n}\ (\frac{T_{0}}{a} + \frac{2\ b}{a^{2}} + \frac {3\ b}{a^{3}} + ... + \frac{n\ b}{a^{n}})= T_{0}\ a^{n-1} + b\ \sum_{k=2}^{n} k\ a^{n-k}$ (2)

Kind regards

$\chi$ $\sigma$