Math puzzle

A sequence is defined as follows:
a(1)=1
a(n+1)=a(n)+1/a(n)

so,
a(2)=2
a(3)=2.5
a(4)=2.9

etc.

a(100) > 14 - true or false? don't use a calculator.

so far i have:

after it gets to 2 each increment is 1/2 or so it needs at least 2 terms to get to 3
after it gets to 3 each increment is 1/3 or so it needs at least 3 terms to get to 4
...
...
after it gets to 13 each increment is 1/13 or so it needs at least 13 terms to get to 14

total terms to get to 13: 13*7=91 crap... let me think about this...

Originally posted by Dejection
so far i have:

after it gets to 2 each increment is 1/2 or so it needs at least 2 terms to get to 3
after it gets to 3 each increment is 1/3 or so it needs at least 3 terms to get to 4
...
...
after it gets to 13 each increment is 1/13 or so it needs at least 13 terms to get to 14

total terms to get to 13: 13*7=91 crap... let me think about this...

just about true

Hint: Solve dy/dx = 1/y subject to an appropriate initial condition, and estimate.

Is there a way to take a limit of the series of a nasty continued fraction?

I spent a good couple of days last week wasting my time on this problem. Yesterday, however, I wrote something down whilst on the loo (too much information, I know...) and today it took me only 5 mins to reap the benefit. So, my solution:

It is easy too see that the nth term of the series b(1) = 1, b(n) = b(n - 1) + 1 / x is given by b(n) = 1 + (n - 1) / x. As n tends to infinity b(n) > a(n), however depending on the x this is not always the case for small n. Thus, let us choose an x such that for small n, a(n) > b(n). These must cross over at some point - let this cross over point be a(100).

In short - choose x such that a(100) = b(100). Then,

Now, assume a(99) is less than or equal to 14, a(99) <= 14. Then,
a(100) <= 14 + 1 / 14 = 14.07
But as b(100) <= 14.07
=> 99 / x + 1 <= 14.07
=>...=> 462 / 61 = 7.57 <= x.

=> b(100) = 99/x + 1 >= 61 * 462 / 99 + 1 = 14.07
=> 14.07 = b(100) = a(100) > 14, and we are done, as the other case, a(99) > 14, is trivial.

I think that is correct, and I apologise for the boringness of it. I feel CronicLeaky's answer is more exciting!

Not sure how exciting it is, but:

Consider the region R of the plane consisting of the union of the rectangles [n,n+1]X[0,a(n+1)-a(n)] for n between 1 and N inclusive. Then on one hand the area A of R is 1/a(1) + 1/a(2) + ... + 1/a(N), by the definition of the sequence. On the other hand, the sum telescopes, so that A = a(N+1) - 1. Hence a(N+1) = 1 + 1/a(1) + 1/a(2) + ... + 1/a(N).

Now we find bounds on A:

Consider the region bounded by the x-axis, the line y = 1, and some curve y = y(x) such that y is differentiable, monotone, y(1) = 1, and y'(n) = 1/y(n) for integers n. y(x) = (2x+1)^(1/2) does the trick. We find that y'(n+1) = y'(n) + y''(n) + y'''(n)/2! + ..., by a Taylor expansion about n, so by some alternating series stuff and repeated differentiation, we get that y'(n+1) <= 1/a(n+1) by induction.

Thus the region under the graph of dy/dx lies inside R, so that A >= y(N) - 1, so that a(N+1) >= y(N). y(99) = 199^(1/2) > 196^(1/2) = 14, so a(100) > 14.

If you wanna see an elegant solution 😛 jusy say🙂

Originally posted by ChronicLeaky
Not sure how exciting it is, but:...

You use previous results, while I just hit it with a stick.

Seeing a hint for an elegant solution would be nice, Mr 113.

Originally posted by Swlabr
You use previous results, while I just hit it with a stick.

Seeing a hint for an elegant solution would be nice, Mr 113.

Square the a(n)'s🙂

Originally posted by Swlabr
You use previous results, while I just hit it with a stick.

Seeing a hint for an elegant solution would be nice, Mr 113.

The ideal solution uses no previous results and hits it with a pretty stick 🙂

I guess what OP wants is:

a(n+1)^2 = 2 + a(n)^2 + 1/a(n)^2 > 2 + a(n)^2

So that by the same telescoping as before, a(n+1)^2 > 2*99 + 1.

Just squaring it is certainly short, but it somehow obscures the issue. In general, nonlinear difference equations like this one are hard to solve -- they're about as hard to solve as the corresponding nonlinear differential equations. In this case, though, the equation a(n+1) - a(n) = 1/a(n) corresponds to the equation dy/dx = 1/y, which just happens to be easy to solve, and the relationship between a(n) and 2n+1 reflects this. Hiding in the malarkey I posted yesterday is also the upper bound a(100)^2 < 2*100 + 1.

Originally posted by ChronicLeaky
The ideal solution uses no previous results and hits it with a pretty stick 🙂

I guess what OP wants is:

a(n+1)^2 = 2 + a(n)^2 + 1/a(n)^2 > 2 + a(n)^2

So that by the same telescoping as before, a(n+1)^2 > 2*99 + 1.

Just squaring it is certainly short, but it somehow obscures the issue. In general, nonlinear difference equations like this on ...[text shortened]... this. Hiding in the malarkey I posted yesterday is also the upper bound a(100)^2 < 2*100 + 1.

I greatly dislike differential equations.

Originally posted by Swlabr
I greatly dislike differential equations.

Me too, actually.

Originally posted by ChronicLeaky
The ideal solution uses no previous results and hits it with a pretty stick 🙂

I guess what OP wants is:

a(n+1)^2 = 2 + a(n)^2 + 1/a(n)^2 > 2 + a(n)^2

So that by the same telescoping as before, a(n+1)^2 > 2*99 + 1.

Just squaring it is certainly short, but it somehow obscures the issue. In general, nonlinear difference equations like this on ...[text shortened]... this. Hiding in the malarkey I posted yesterday is also the upper bound a(100)^2 < 2*100 + 1.

What do you mean by telescoping?

Originally posted by Palynka
What do you mean by telescoping?

He is, I believe, referring to this part of his proof,
"On the other hand, the sum telescopes, so that A = a(N+1) - 1. Hence a(N+1) = 1 + 1/a(1) + 1/a(2) + ... + 1/a(N)".

Otherwise, I've never came across the term before...