How Does Induction Prove the Formula for Terms in a Recurrence Relation?

[quasar987]

We want to show that the nth + 1 term of a sequence that is defined as x_{n+1} = b + ax_n, n\geq1 \ a,b \in \mathbb{R} is given by

x_{n+1} = a^nx_1 + b\frac{1-a^n}{1-a} \ \mbox{if} \ a\neq 1

The manual suggests that we proceed by induction. Let us proceed by induction.

P(1) is that

x_{1+1}=x_2=a^1x_1+b\frac{1-a^1}{1-a}

x_2=b+ax_1,

which is in agreement with the expression of x_2 implied by the definition of x_{n+1}

Let us suppose P(n) to be true, i.e. that x_{n+1} is in fact

x_{n+1}=a^nx_1+b\frac{1-a^n}{1-a}

And let's see if P(n)being true implies that P(n+1) is true. P(n+1) is that

x_{n+1+1}=x_{n+2}=a^{n+1}x_1+b\frac{1-a^{n+1}}{1-a}

but after "simplifing" to

x_{n+2}=aa^nx_1+b\frac{1-aa^n}{1-a}[/itex],<br /> <br /> I don&#039;t see how to go any further than that!

 

[Fredrik]

The word you're looking for is "sequence" (but I see you figured that out while I was writing this), and I believe that this is the piece of the calculation you're missing:

x_{(n+1)+1}=b+ax_{n+1}=b+a\bigg(a^n x_1+b\frac{1-a^n}{1-a}\bigg)=b+a^{n+1}x_1+ab\frac{1-a^n}{1-a}=a^{n+1}x_1+b\bigg(1+a\frac{1-a^n}{1-a}\bigg)=
=a^{n+1}x_1+b\frac{1-a+a(1-a^n)}{1-a}=a^{n+1}x_1+b\frac{1-a^{n+1}}{1-a}

 

[quasar987]

Ah yes! Very clever! Thanks Fredrik!