Increasing sequence by induction

[petrol.veem]

I've been trying to solve this interesting sequence from my calc textbook:

a(1) = 1, a(n+1) = (1+2a(n)) / (1+a(n))

So I've found the first 5 terms of the sequence as follows:

a(1) = 1
a(2) = 3/2
a(3) = 8/5
a(4) = 21/13
a(5) = 55/34

Now it is asking me to show that the sequence increases by induction.

I am trying to somehow relate a(k+1) > a(k) to show that the sequence is increasing.

However, I'm not exactly sure how to go about doing so. Do I need to find the limit of the sequence?

 

[soroban]

Hello, petrol.veem!

I don't have an inductive proof yet, but I have some observations.
. . Maybe they'll insprire you . . .

\(\displaystyle a(1) \:=\:1,\;\; a(n+1) \:= \:\frac{1+2a(n)}{1+a(n)}\)

So I've found the first 5 terms of the sequence as follows:

. . \(\displaystyle \begin{array}{ccc}a(1) &=& 1 \\a(2) &= &\frac{3}{2} \\ a(3) &= &\frac{8}{5} \\ a(4) &= &\frac{21}{13} \\ a(5) &= &\frac{55}{34} \end{array}\)

Now it is asking me to show that the sequence increases by induction.

I am trying to somehow relate \(\displaystyle a(k+1) \,> \,a(k)\) to show that the sequence is increasing.

However, I'm not exactly sure how to go about doing so. Do I need to find the limit of the sequence?

\(\displaystyle \text{Note that: }\;a(n+1) \;=\;\frac{1 + 2a(n)}{1 + a(n)} \;=\;2 - \frac{1}{1 + a(n)}\)

\(\displaystyle \text{Hence, each term is 2 ... minus an ever-decreasing fraction.}\)



\(\displaystyle \text{In your list, note that each fraction is the ratio of two consecutive Fibonacci numbers.}\)
. . \(\displaystyle \text{Fibonacci sequence: }\;1,\,1,\,2,\,3,\,5,\,8,\,13,\,21,\,34,\,55,\,89,\,\hdots\)

\(\displaystyle \text{Hence, we have: }\;a(n) \:=\:\frac{F(2n)}{F(2n-1)}\)

\(\displaystyle \text{And it is well known that this ratio approaches }\phi = 1.61803...\)

 

[pka]

Using the rewritten sequence the way Soroban did we can use induction.
If it is true that \(\displaystyle a_{K + 1} > a_K\) we show it is true for K+1.
\(\displaystyle \begin{array}{l} a_{K + 1} > a_K \\ 1 + a_{K + 1} > 1 + a_K \\ \frac{1}{{1 + a_{K + 1} }} < \frac{1}{{1 + a_K }} \\ - \frac{1}{{1 + a_{K + 1} }} > - \frac{1}{{1 + a_K }} \\ 2 - \frac{1}{{1 + a_{K + 1} }} > 2 - \frac{1}{{1 + a_K }} \\ a_{K + 2} > a_{K + 1} \\ \end{array}\)

 

[petrol.veem]

Ok, this is starting to make sense...

But how does one go about showing that the limit is in fact 1.618...?

When I was trying to work it out, I came up with:

lim(n-->infinity) [ a(n) ] = L

lim(n-->infinity) [ (1 + 2a(n-1)) / (1 + a(n-1)) ] = L

(1 + 2L) / (1 + L) = L

...

L^2 - L - 1 = 0

which I couldn't solve in my head.

Is this looking at all right?

 

[pka]

lim(n-->infinity) [ (1 + 2a(n-1)) / (1 + a(n-1)) ] = L
(1 + 2L) / (1 + L) = L
L^2 - L - 1 = 0

Use the quadric formula.

 

[Deleted member 4993]

Ok, this is starting to make sense...

But how does one go about showing that the limit is in fact 1.618...?

When I was trying to work it out, I came up with:

lim(n-->infinity) [ a(n) ] = L

lim(n-->infinity) [ (1 + 2a(n-1)) / (1 + a(n-1)) ] = L

(1 + 2L) / (1 + L) = L

...

L^2 - L - 1 = 0

\(\displaystyle L_{1,2} \, = \, \frac{1\,\pm\,\sqrt{5}}{2} = 1.618033989 \, , \, -0.618033989\)



which I couldn't solve in my head. <-- Normal people would at least need pencil-paper for that

Is this looking at all right?