Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 14 Feb '09 22:45
    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.
  2. 18 Feb '09 08:30
    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...
  3. 23 Feb '09 20:06
    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
  4. Standard member ChronicLeaky
    Don't Fear Me
    23 Feb '09 20:26
    Hint: Solve dy/dx = 1/y subject to an appropriate initial condition, and estimate.
  5. Subscriber joe shmo
    Strange Egg
    24 Feb '09 02:48
    Is there a way to take a limit of the series of a nasty continued fraction?
  6. 24 Feb '09 10:02 / 1 edit
    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!
  7. Standard member ChronicLeaky
    Don't Fear Me
    24 Feb '09 20:00
    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.
  8. 24 Feb '09 21:39
    If you wanna see an elegant solution jusy say
  9. 25 Feb '09 08:13 / 1 edit
    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.
  10. 25 Feb '09 11:43
    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
  11. Standard member ChronicLeaky
    Don't Fear Me
    25 Feb '09 15:08
    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.
  12. 25 Feb '09 15:21
    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.
  13. Standard member ChronicLeaky
    Don't Fear Me
    25 Feb '09 15:41
    Originally posted by Swlabr
    I greatly dislike differential equations.
    Me too, actually.
  14. Standard member Palynka
    Upward Spiral
    25 Feb '09 15:43
    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?
  15. 25 Feb '09 15:57
    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...