Sqrt(2) as a sequence

[akoaysigod]

If an = 1 and an+1 = 1 + 1/1+an

then show that the limit as n approaches inifinity = sqrt(2)
Argue why this shows

sqrt(2) = 1+1/2 + 1/2+ 1/2+... etc This is supposed to be a continued fraction but I'm not sure how to write that in a way that would like nice.

Anyway, I'm supposed to use induction to get the answer.

I know that is a2n+1 is increasing and is bounded above just from plugging numbers in really. And a2n is decreasing and is bounded below, through the same method. Therefore a2n+2 > a2n and

Base case: a4 < a2 and a2n+1 < a4n+1
Now this is where I start to get confused because I haven't really had to much experience using induction nor have I seen too many examples. For the former part I know it looks something like...

a2k+2 < a2k
a2k+4 < a2k+2
a2k+2 = 1 + 1/(1+a2k + 1) where I really start to get confused
1 + a2k+2 < 1 +a2k
1/1+a2k+2 > 1/1+a2k

I'm not even sure where this is going really or why this proves anything. Any help would be much appreciated. Thanks.

 

[Deleted member 4993]

If an = 1 and an+1 = 1 + 1/1+an

then show that the limit as n approaches inifinity = sqrt(2)
Argue why this shows

sqrt(2) = 1+1/2 + 1/2+ 1/2+... etc


Are you sure? The above does not look anything like a[sub:1896c06o]n+1[/sub:1896c06o] = 1 + 1/(1+a[sub:1896c06o]n[/sub:1896c06o])

Please be extra careful while posting your problem - otherwise it is wastage of your time and our time.

This is supposed to be a continued fraction but I'm not sure how to write that in a way that would like nice.

Anyway, I'm supposed to use induction to get the answer.

I know that is a2n+1 is increasing and is bounded above just from plugging numbers in really. And a2n is decreasing and is bounded below, through the same method. Therefore a2n+2 > a2n and

Base case: a4 < a2 and a2n+1 < a4n+1
Now this is where I start to get confused because I haven't really had to much experience using induction nor have I seen too many examples. For the former part I know it looks something like...

a2k+2 < a2k
a2k+4 < a2k+2
a2k+2 = 1 + 1/(1+a2k + 1) where I really start to get confused
1 + a2k+2 < 1 +a2k
1/1+a2k+2 > 1/1+a2k

I'm not even sure where this is going really or why this proves anything. Any help would be much appreciated. Thanks.

 

[soroban]

Hello, akoaysigod!

\(\displaystyle \text{If }\,a_n = 1\,\text{ and }\,a_{n+1} \:=\: 1 + \frac{1}{1+a_n }}\)

. . \(\displaystyle \text{then show that: }\;\lim_{n\to\infty}a_n \:=\: \sqrt{2}\)

\(\displaystyle \text{Argue why this shows: }\;\sqrt{2} \:=\: 1+\frac{1}{2 + \frac{1}{2+ \frac{1}{2 + \hdots}}}}\)

I'm still working on the inductive proof,
. . but I can prove the last part directly.

\(\displaystyle \text{Let: }\;x \;=\;1 +\frac{1}{2+\frac{1}{2+\frac{1}{2+\hdots}}}}\)

\(\displaystyle \text{Add 1 to both sides: }\;x + 1 \;=\;2 + \frac{1}{\underbrace{\left(2+\frac{1}{2 + \frac{1}{2+\hdots}}\right)}_{\text{This is }x+1}}\)

\(\displaystyle \text{Then we have: }\;x + 1 \;=\;2 + \frac{1}{x+1}\)

. . \(\displaystyle \text{which simplifies to: }\;x^2 \:=\:2 \quad\Rightarrow\quad x \:=\:\sqrt{2}\)

 

[chrisr]

With "Proof by Induction" being the "gunpowder effect" or "Japanese dominoes" effect,
it would not be used to find what value a[sub:2ck66mz9]n[/sub:2ck66mz9] converges to.

Proof By Induction utilises the relationship
if a[sub:2ck66mz9]n[/sub:2ck66mz9] is valid and a[sub:2ck66mz9]n+1[/sub:2ck66mz9] is valid BECAUSE OF THAT, then
a[sub:2ck66mz9]1[/sub:2ck66mz9] valid makes a[sub:2ck66mz9]2[/sub:2ck66mz9] valid makes a[sub:2ck66mz9]3[/sub:2ck66mz9] valid makes all a[sub:2ck66mz9]n[/sub:2ck66mz9] valid
in cases where we are trying to formulate a pattern or prove a relationship.

We could say that an observation is already formulated if

a[sub:2ck66mz9]1[/sub:2ck66mz9]=1, a[sub:2ck66mz9]2[/sub:2ck66mz9]=1+1/(1+a[sub:2ck66mz9]1[/sub:2ck66mz9]), a[sub:2ck66mz9]n[/sub:2ck66mz9]=1+1/(1+a[sub:2ck66mz9]n-1[/sub:2ck66mz9]),
for n being natural numbers without zero.

If a[sub:2ck66mz9]n[/sub:2ck66mz9] converges on a value as n approaches infinity, then a[sub:2ck66mz9]infinity[/sub:2ck66mz9]=a[sub:2ck66mz9]infinity-1[/sub:2ck66mz9]

Therefore, a[sub:2ck66mz9]infinity[/sub:2ck66mz9] =1+1/(1+a[sub:2ck66mz9]infinity[/sub:2ck66mz9])

so a[sub:2ck66mz9]infinity[/sub:2ck66mz9]=(1+a[sub:2ck66mz9]infinity[/sub:2ck66mz9]+1)/(1+a[sub:2ck66mz9]infinity[/sub:2ck66mz9])

a[sub:2ck66mz9]infinity[/sub:2ck66mz9]+(a[sub:2ck66mz9]infinity[/sub:2ck66mz9])[sup:2ck66mz9]2[/sup:2ck66mz9]=a[sub:2ck66mz9]infinity[/sub:2ck66mz9]+2

(a[sub:2ck66mz9]infinity[/sub:2ck66mz9])[sup:2ck66mz9]2[/sup:2ck66mz9]=2

It seems that because this is the result "if" a[sub:2ck66mz9]n[/sub:2ck66mz9] converges as n approaches infinity,
then Proof by Induction is utilised to prove for convergence in this case
by showing that the graph of a[sub:2ck66mz9]n[/sub:2ck66mz9] versus n keeps increasing
or decreasing by smaller and smaller amounts as n approaches infinity.
A couple of different graphs could be examined, converging on an upper or lower limit.
We can't test for convergence the normal way because a[sub:2ck66mz9]n[/sub:2ck66mz9] is not formulated in terms of n.

I think that's the idea. I must have another look at this later

 

[chrisr]

What I got when I continued is the following question

is {1-2(a[sub:h6kkrske]n[/sub:h6kkrske])[sup:h6kkrske]2[/sup:h6kkrske]}/(2a[sub:h6kkrske]n[/sub:h6kkrske]+3) < 2-(a[sub:h6kkrske]n[/sub:h6kkrske])[sup:h6kkrske]2[/sup:h6kkrske] ?

using the criteria for convergence a[sub:h6kkrske]n+2[/sub:h6kkrske]-a[sub:h6kkrske]n+1[/sub:h6kkrske] must be < a[sub:h6kkrske]n+1[/sub:h6kkrske]-a[sub:h6kkrske]n[/sub:h6kkrske]

If this is the case then Proof by Induction is "built in" as that will follow for every pair of adjacent terms
all the way to infinity.

Since a[sub:h6kkrske]n[/sub:h6kkrske]>1 then the left side is negative
and since a[sub:h6kkrske]n[/sub:h6kkrske] is also <2 due to the fact we are adding a fraction <1 to 1,
then the right side is positive.

Hence, as n approaches infinity, a[sub:h6kkrske]n[/sub:h6kkrske] converges on a value,
which must be sqrt(2) as we have already discovered.

I can include the calculations (will take ages), but what I did was to express a[sub:h6kkrske]n+2[/sub:h6kkrske] and a[sub:h6kkrske]n+1[/sub:h6kkrske]
in terms of a[sub:h6kkrske]n[/sub:h6kkrske] first.

 

[chrisr]

Sorry about this but there's a flaw in my analysis!
a[sub:38y58xde]n[/sub:38y58xde] starts at 1, goes to 1.5 and is decreasing after that.

I assumed (yellow card for me) that the graph was "increasing".

Also, there is a second blunder in my above post regarding the right side being positive.

I have to redo the analysis, as my inequality is the wrong way around
and I'm not sure this will solve for convergence.
No doubt there may be a simpler way.

 

[akoaysigod]

Are you sure? The above does not look anything like an+1 = 1 + 1/(1+an)

Please be extra careful while posting your problem - otherwise it is wastage of your time and our time.

I'm sorry, I should have posted a link to what it looked like but other people have posted it since then. Also I made a mistake
an doesn't = 1 but a1 = 1 and then a2 = 3/2 etc. I'm not entirely sure what an would equal or its place in this problem if it were to be isolated although I don't think that's possible since it relies on everything else.

Anyway, thanks for the help, I went in today to get extra help on this but am more or less still very confused. Fortunately there was another part to the question so I'll at least get partial credit and its only 1/5 of the homework and I'm fairly confident in my answers to the other problems. I'm just going to hand in what I've done so far and cut my losses on this and work on some other things. I'm sure I'll run into induction again someday and hopefully I'll be better equipped to handle it.

If anyone is interested, if and when I get the solutions for this I'll post it. It'll be in .pdf format so I won't have to try an type it out.

 

[chrisr]

Sorry I was not more careful with my calculations.

a[sub:t45iwpz7]n[/sub:t45iwpz7] is in fact in the shape of a sawtooth with the peaks coming closer and closer as n increases.

a[sub:t45iwpz7]1[/sub:t45iwpz7]=1, a[sub:t45iwpz7]2[/sub:t45iwpz7]=1.5, a[sub:t45iwpz7]3[/sub:t45iwpz7]=1.4, a[sub:t45iwpz7]4[/sub:t45iwpz7]=1.417, a[sub:t45iwpz7]5[/sub:t45iwpz7]=1.4138,
a[sub:t45iwpz7]n[/sub:t45iwpz7] is increasing and decreasing for alternate terms, it's "homing in" on sqrt(2),

I guess the thing to do is prove that these positive and negative "increments"
are constantly decreasing in magnitude.
We can clearly see it's homing in.
The thing is to prove that beyond all doubt as a formulation.

 

[chrisr]

Sorry for missing your deadline Akoaysigod,
very busy yesterday unfortunately.

I think I've got it, belatedly.

If we examine the sequence, we have
a[sub:1q3zct2r]1[/sub:1q3zct2r]=1, a[sub:1q3zct2r]2[/sub:1q3zct2r]=1.5, a[sub:1q3zct2r]3[/sub:1q3zct2r]=1.4, a[sub:1q3zct2r]4[/sub:1q3zct2r]=1.417, a[sub:1q3zct2r]5[/sub:1q3zct2r]=1.4138.

It may be better to examine the terms expressed as fractions instead,
but what we "appear" to have is a digitized sawtooth, with the terms going above and below
a line, with the terms closing in on the line as n continues to increase.
From the earlier discussions, if this really is the situation, then the line is sqrt(2) above zero,
if a[sub:1q3zct2r]n[/sub:1q3zct2r] is plotted on the vertical axis.

We could try to prove that the positive increments are constantly decreasing and the negative ones
also constantly decreasing using (a[sub:1q3zct2r]2n[/sub:1q3zct2r]-a[sub:1q3zct2r]2n-1[/sub:1q3zct2r]) < (a[sub:1q3zct2r]2n-2[/sub:1q3zct2r]-a[sub:1q3zct2r]2n-3[/sub:1q3zct2r])
for the positive increments,
and (a[sub:1q3zct2r]2n[/sub:1q3zct2r]-a[sub:1q3zct2r]2n+1[/sub:1q3zct2r]) < (a[sub:1q3zct2r]2n-2[/sub:1q3zct2r]-a[sub:1q3zct2r]2n-1[/sub:1q3zct2r]) for the negative ones

or simply use the modulus of a[sub:1q3zct2r]n+2[/sub:1q3zct2r]-a[sub:1q3zct2r]n+1[/sub:1q3zct2r] should be < the modulus of a[sub:1q3zct2r]n+1[/sub:1q3zct2r]-a[sub:1q3zct2r]n[/sub:1q3zct2r]

Doing this is in fact utilising Proof by Induction,
though I suspect it may have another description.
The reason is that we are checking that any increment is smaller than the preceding one,
which is the spirit of Proof by Induction.
We notice the pattern with the values of the first few a[sub:1q3zct2r]n[/sub:1q3zct2r] terms,
then we prove that a[sub:1q3zct2r]n[/sub:1q3zct2r] is homing in on the sqrt(2) by examining how a[sub:1q3zct2r]n[/sub:1q3zct2r] is changing
in general.

If we write a[sub:1q3zct2r]n+2[/sub:1q3zct2r] and a[sub:1q3zct2r]n+1[/sub:1q3zct2r] in terms of a[sub:1q3zct2r]n[/sub:1q3zct2r],
we get a[sub:1q3zct2r]n+1[/sub:1q3zct2r] = 1+1/{1+a[sub:1q3zct2r]n[/sub:1q3zct2r]} = (2+a[sub:1q3zct2r]n[/sub:1q3zct2r])/(1+a[sub:1q3zct2r]n[/sub:1q3zct2r])
and a[sub:1q3zct2r]n+2[/sub:1q3zct2r] = (4+3a[sub:1q3zct2r]n[/sub:1q3zct2r])/(3+2a[sub:1q3zct2r]n[/sub:1q3zct2r]).

When we examine the moduli of the increments, we get the question

Is modulus{a[sub:1q3zct2r]n+2[/sub:1q3zct2r]-a[sub:1q3zct2r]n+1[/sub:1q3zct2r]} < modulus{a[sub:1q3zct2r]n+1[/sub:1q3zct2r]-a[sub:1q3zct2r]n[/sub:1q3zct2r]} ?

eventually giving......
is modulus{[(a[sub:1q3zct2r]n[/sub:1q3zct2r])[sup:1q3zct2r]2[/sup:1q3zct2r]-2]/[3+2a[sub:1q3zct2r]n[/sub:1q3zct2r]]} < modulus{[(a[sub:1q3zct2r]n[/sub:1q3zct2r])[sup:1q3zct2r]2[/sup:1q3zct2r]-2]/[1+a[sub:1q3zct2r]n[/sub:1q3zct2r]]} ?

which means, since the numerators are the same, then the left fraction is < the right if it's denominator is > the right one's...
is (3+2a[sub:1q3zct2r]n[/sub:1q3zct2r]) > (1+a[sub:1q3zct2r]n[/sub:1q3zct2r]) ? Yes, as a[sub:1q3zct2r]n[/sub:1q3zct2r] is positive

 

[chrisr]

A very simple proof is

[sqrt(2)-1][sqrt(2)+1]=2+sqrt(2)-sqrt(2)-1=2-1=1
[sqrt(3)-1][sqrt(3)+1]=3-1=2
[sqrt(x)-1][sqrt(x)+1]=x-1

Hence sqrt(x)-1=(x-1)/(1+sqrt(x))
sqrt(x)=1+(x-1)/(1+sqrt(x))

If the numerator is 1 then x-1=1 so x=2.

The denominator is also an infinite "nested fraction" as we can keep relacing the
sqrt(x) with 1+(x-1)/(1+sqrt(x))