Cracking a Problem: Solving $a_n$ with $a_1$

[anemone]

Hi MHB,

I worked with this problem for at least an hour but I don't see how to crack it using my way (which I will show below)...I was wondering if my way of thinking is just plain wrong and I won't be able to get anywhere with it.(Angry)

Problem:

Let $a_n$ be a sequence of positive real numbers defined by $a_1=1$ and $a_{n+1}=a_n+\dfrac{1}{a_n}$ for $n \ge 1$.

Find $\lfloor a_{100000} \rfloor$.

Attempt:

I tried to solve the problem by relating $a_2, a_3, a_4, a_5, a_6, a_7$ etc to $a_1$, which is 1 and hopefully I could "deduce" some useful pattern from it but to no avail...

$a_1=1$

$a_2=\dfrac{a_1}{1}+\dfrac{1}{a_1}=1+\dfrac{1}{1}=2$

$a_3=a_2+\dfrac{1}{a_2}=a_1+\dfrac{1}{a_1}+\dfrac{1}{\left(a_1+\dfrac{1}{a_1} \right)}=\dfrac{a_1^2+1}{a_1}+\dfrac{a_1}{a_1^2+1}$

$a_4=a_3+\dfrac{1}{a_3}=\dfrac{a_1^2+1}{a_1}+ \dfrac{a_1}{a_1^2+1}+\dfrac{1}{\left(\dfrac{a_1^2+1}{a_1}+\dfrac{a_1}{a_1^2+1} \right)}=\dfrac{(a_1+1)^2+a_1^2}{a_1(a_1^2+1)}+ \dfrac{a_1(a_1^2+1)}{(a_1+1)^2+a_1^2}$

If I am allowed to conclude at this juncture that I find we can relate $a_n$ and its previous term, $a_{n-1}$ in the following manner:

$a_n$ is the sum of two fractions where the second fraction is the reciprocal of the first fraction and the first fraction, its numerator is the sum of the two square terms of the two numerators of the previous term ($a_{n-1})$ and the denominator of it would be the product of the two numerators of that previous term.

But I really don't see how this is going to help because I am incapable of "deducing" a correct general formula for $a_n$ based on my observation and hence I hope someone could help me with this hard (at least for me) problem.

Thanks in advance.

 

[alyafey22]

$$a_{n+1}=a_n+\dfrac{1}{a_n}$$

The sequence is an increasing unbounded sequence. I am not sure if we can find a general formula for $$a_n$$.

 

[anemone]

$$a_{n+1}=a_n+\dfrac{1}{a_n}$$

The sequence is an increasing unbounded sequence. I am not sure if we can find a general formula for $$a_n$$.

How could I not realize that...thanks for pointing this out for me, ZaidAlyafey!

Hmm...with this in mind, I think I can refine what I have found to see if I could proceed...I will write back if I solve it but if I don't, please feel free to show me the right way to tackle it. Thank you so much in advance.

 

[chisigma]

Hi MHB,

I worked with this problem for at least an hour but I don't see how to crack it using my way (which I will show below)...I was wondering if my way of thinking is just plain wrong and I won't be able to get anywhere with it.(Angry)

Problem:

Let $a_n$ be a sequence of positive real numbers defined by $a_1=1$ and $a_{n+1}=a_n+\dfrac{1}{a_n}$ for $n \ge 1$.

Find $\lfloor a_{100000} \rfloor$.

Attempt:

I tried to solve the problem by relating $a_2, a_3, a_4, a_5, a_6, a_7$ etc to $a_1$, which is 1 and hopefully I could "deduce" some useful pattern from it but to no avail...

$a_1=1$

$a_2=\dfrac{a_1}{1}+\dfrac{1}{a_1}=1+\dfrac{1}{1}=2$

$a_3=a_2+\dfrac{1}{a_2}=a_1+\dfrac{1}{a_1}+\dfrac{1}{\left(a_1+\dfrac{1}{a_1} \right)}=\dfrac{a_1^2+1}{a_1}+\dfrac{a_1}{a_1^2+1}$

$a_4=a_3+\dfrac{1}{a_3}=\dfrac{a_1^2+1}{a_1}+ \dfrac{a_1}{a_1^2+1}+\dfrac{1}{\left(\dfrac{a_1^2+1}{a_1}+\dfrac{a_1}{a_1^2+1} \right)}=\dfrac{(a_1+1)^2+a_1^2}{a_1(a_1^2+1)}+ \dfrac{a_1(a_1^2+1)}{(a_1+1)^2+a_1^2}$

If I am allowed to conclude at this juncture that I find we can relate $a_n$ and its previous term, $a_{n-1}$ in the following manner:

$a_n$ is the sum of two fractions where the second fraction is the reciprocal of the first fraction and the first fraction, its numerator is the sum of the two square terms of the two numerators of the previous term ($a_{n-1})$ and the denominator of it would be the product of the two numerators of that previous term.

But I really don't see how this is going to help because I am incapable of "deducing" a correct general formula for $a_n$ based on my observation and hence I hope someone could help me with this hard (at least for me) problem.

Thanks in advance.

The difference equation...

$\displaystyle a_{n+1} = a_{n} + \frac{1}{a_{n}}\ (1)$

... can be used to find an approximate solution of the ODE...

$\displaystyle y^{\ '} = \frac{1}{y}\ (2)$

... which has the exact solution $\displaystyle y= \sqrt{2\ x + c}$. If we adopt c=0 and suppose $a_{n} \sim \sqrt{2\ n} = b_{n}$ we obtain...

$a_{1} = 1,\ b_{1} = 1.414...$

$a_{2} = 2,\ b_{2} = 2$

$a_{3} = 2.5,\ b_{3} = 2.449...$

$a_{4} = 2.9,\ b_{4} = 2.828...$

$a_{5} = 3.244...,\ b_{5} = 3.162...$

$a_{6} = 3.553...,\ b_{6} = 3.464...$

$a_{7} = 3.834...,\ b_{7} = 3.741...$

$a_{8} = 4.095,\ b_{8} = 4$

$a_{9} = 4.339...,\ b_{9} = 4.242...$

$a_{10} = 4.569...,\ b_{10} = 4.472...$

Kind regards $\chi$ $\sigma$

 

[Opalg]

Let $a_n$ be a sequence of positive real numbers defined by $a_1=1$ and $a_{n+1}=a_n+\dfrac{1}{a_n}$ for $n \ge 1$.

Find $\lfloor a_{100000} \rfloor$.

Warning! This is a sledgehammer attack on the problem, not proper mathematics (more like an engineer's approach).

If $a_n$ lies between $k$ and $k+1$, then $a_{n+1} - a_n$ lies between $\dfrac1{k+1}$ and $\dfrac1k$, say roughly $\dfrac1{k+\frac12}$ on average. So it will take approximately $k+\frac12$ steps for $a_n$ to increase from $k$ to $k+1$. Thus the total number of steps for $a_n$ to go from its initial value $1$ to the value $k$ will be roughly $(1+\frac12) + (2+\frac12) + \ldots + (k-\frac12)$, or (even more roughly) $\frac12k^2.$ But if $\frac12k^2 = n$ then $k = \sqrt{2n}$. If $n= 100000$ then $\sqrt{2n} = \sqrt{200000} \approx 447.2$. Therefore $\lfloor a_{100000} \rfloor = 447.$

As I said, that is in no way mathematically justified, but I expect that answer to be correct. Interestingly, it agrees with chisigma's formula reached from a differential equations standpoint.

 

[anemone]

The difference equation...

$\displaystyle a_{n+1} = a_{n} + \frac{1}{a_{n}}\ (1)$

... can be used to find an approximate solution of the ODE...

$\displaystyle y^{\ '} = \frac{1}{y}\ (2)$

... which has the exact solution $\displaystyle y= \sqrt{2\ x + c}$. If we adopt c=0 and suppose $a_{n} \sim \sqrt{2\ n} = b_{n}$ we obtain...

$a_{1} = 1,\ b_{1} = 1.414...$

$a_{2} = 2,\ b_{2} = 2$

$a_{3} = 2.5,\ b_{3} = 2.449...$

$a_{4} = 2.9,\ b_{4} = 2.828...$

$a_{5} = 3.244...,\ b_{5} = 3.162...$

$a_{6} = 3.553...,\ b_{6} = 3.464...$

$a_{7} = 3.834...,\ b_{7} = 3.741...$

$a_{8} = 4.095,\ b_{8} = 4$

$a_{9} = 4.339...,\ b_{9} = 4.242...$

$a_{10} = 4.569...,\ b_{10} = 4.472...$

Kind regards $\chi$ $\sigma$

Thank you chisigma for showing me the proper way to approach the problem through the ODE route. I appreciate it!

Warning! This is a sledgehammer attack on the problem, not proper mathematics (more like an engineer's approach).

If $a_n$ lies between $k$ and $k+1$, then $a_{n+1} - a_n$ lies between $\dfrac1{k+1}$ and $\dfrac1k$, say roughly $\dfrac1{k+\frac12}$ on average. So it will take approximately $k+\frac12$ steps for $a_n$ to increase from $k$ to $k+1$. Thus the total number of steps for $a_n$ to go from its initial value $1$ to the value $k$ will be roughly $(1+\frac12) + (2+\frac12) + \ldots + (k-\frac12)$, or (even more roughly) $\frac12k^2.$ But if $\frac12k^2 = n$ then $k = \sqrt{2n}$. If $n= 100000$ then $\sqrt{2n} = \sqrt{200000} \approx 447.2$. Therefore $\lfloor a_{100000} \rfloor = 447.$

As I said, that is in no way mathematically justified, but I expect that answer to be correct. Interestingly, it agrees with chisigma's formula reached from a differential equations standpoint.

Hi Opalg, thanks to you too for teaching me another way to look at the problem.

Edit: When I first saw the first remark from Opalg that is in red, I thought I have done something wrong! I remember there was a time I committed a serious silly blunder and even though I had fixed it, I quickly logged out MHB when I saw Opalg logged in our site, for fear of being spotted by him.(Tmi)

 

[chisigma]

... when I first saw the first remark from Opalg that is in red, I thought I have done something wrong! I remember there was a time I committed a serious silly blunder and even though I had fixed it, I quickly logged out MHB when I saw Opalg logged in our site, for fear of being spotted by him...(Tmi)

Don't worry anemone, that is all right!... You have to know that Opalg and I are two 'old wolves' ... but wolves of different species!... He is a 'Mathematician' and what really matters is 'rigour'... I'm an 'Engineer' and what really matters is 'fast result'... and the rigour can solved later 'taking it easy'...

... the 'red written' is no more that a 'soft hammer blow' we are used to do each other sometime ...

Kind regards

$\chi$ $\sigma$

 

[Opalg]

Don't worry anemone, that is all right!... You have to know that Opalg and I are two 'old wolfs'... but wolfs of different species!... He is a 'Mathematician' and what really matters is 'rigour'... I'm an 'Engineer' and what really matters is 'fast result'... and the rigour can solved later 'taking it easy'...

... the 'red written' is no more that a 'soft hammer blow' we are used to do each other sometime ...

Kind regards

$\chi$ $\sigma$

@ chisigma: The red writing referred to my own approach, which I wrote before seeing yours. In fact, the differential equations approach is much more like "real mathematics" than the informal method that I used. So I think that I'm the "engineer" and you are the mathematician here.

The wolf metaphor reminds me of an interesting quotation about foxes. In his autobiography (1956), Norbert Wiener wrote of his collaboration with R.E.A.C.Paley, a brilliant young student of G.H.hardy's collaborator J.E.Littlewood, who died very young in a skiing accident:

He brought me a superb mastery of mathematics as a game and a vast number of tricks that added up to an armament by which almost any problem could be attacked, yet he had almost no sense of the orientation of mathematics among the other sciences. In many problems which we undertook I saw, as was my habit, a physical and even an engineering application, and my sense of this often determined the images I formed and the tools by which I sought to solve my problems. Paley was eager to learn my ways, as I was eager to learn his, but my applied point of view did not come easily to him, nor, I think, did he regard it as fully sportsmanlike. I must have shocked him and my other English friends by my willingness to shoot a mathematical fox if I could not follow it with the hunt.​

Despite coming from the English tradition of Hardy and Paley, I completely agree with Wiener that mathematical insight can come from many different directions. We may be wolves of different species, but we hunt in the same pack.

 

[chisigma]

@ chisigma: The red writing referred to my own approach, which I wrote before seeing yours. In fact, the differential equations approach is much more like "real mathematics" than the informal method that I used. So I think that I'm the "engineer" and you are the mathematician here.

The wolf metaphor reminds me of an interesting quotation about foxes. In his autobiography (1956), Norbert Wiener wrote of his collaboration with R.E.A.C.Paley, a brilliant young student of G.H.hardy's collaborator J.E.Littlewood, who died very young in a skiing accident:

He brought me a superb mastery of mathematics as a game and a vast number of tricks that added up to an armament by which almost any problem could be attacked, yet he had almost no sense of the orientation of mathematics among the other sciences. In many problems which we undertook I saw, as was my habit, a physical and even an engineering application, and my sense of this often determined the images I formed and the tools by which I sought to solve my problems. Paley was eager to learn my ways, as I was eager to learn his, but my applied point of view did not come easily to him, nor, I think, did he regard it as fully sportsmanlike. I must have shocked him and my other English friends by my willingness to shoot a mathematical fox if I could not follow it with the hunt.​

Despite coming from the English tradition of Hardy and Paley, I completely agree with Wiener that mathematical insight can come from many different directions. We may be wolves of different species, but we hunt in the same pack.

The best answer I ever received!... thank You! (Emo)...

Kind regards

$\chi$ $\sigma$

P.S. ... my poor knowledge of English language caused me to write 'wolfs' instead of 'wolves'... very sorry!(Nerd)... P.P.S. ... the 'historic note' of Opalg is very interesting and I remember that one time I proposed to create on MHB an "History of Mathematic forum'... I'm sure that in such a forum Opalg and I will contribute very much!...

 

[chisigma]

... R.E.A.C.Paley, a brilliant young student of G.H.hardy's collaborator J.E.Littlewood, who died very young in a skiing accident...

View attachment 1845

Kind regards

$\chi$ $\sigma$