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

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

 

[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!