1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to solve this recurrence

  1. Nov 17, 2014 #1
    1. The problem statement, all variables and given/known data
    If
    ##T(n+1)=T(n)+ \lfloor \sqrt{n+1} \rfloor , n \geq 1##
    ##T(1)=1##
    then
    ##T(m^2) = ? , m \geq 1##

    2. Relevant equations


    3. The attempt at a solution
    ##T(n)=T(n+1) - \lfloor \sqrt{n+1} \rfloor , n \geq 1##
    ##T(m^2)=T(m^2+1) - \lfloor \sqrt{m^2+1} \rfloor##
    ...
    ##T(m^2)= \sqrt{m^2+m} - ... - \sqrt{m^2+3} - \sqrt{m^2+2} - \sqrt{m^2+1}##
     
    Last edited: Nov 17, 2014
  2. jcsd
  3. Nov 17, 2014 #2

    jedishrfu

    Staff: Mentor

    It looks like you're trying to create a generator function T(n+1) where n+1 is m^2 so rather than juggle the formula as you did solving for m^2

    you could say n+1 = m^2 and hence n=m^2 - 1 and sub that in for each n
     
  4. Nov 18, 2014 #3
    Your saying it this way
    ##T(n+1) = T(n) + \lfloor \sqrt{n+1} \rfloor##
    ##m^2 = n + 1##
    ##T(m^2) = T(m^2 - 1) + \lfloor \sqrt{m^2} \rfloor##
    on solving it through recursion tree method I'm coming up with
    ##T(m^2) = m + \sqrt{m^2-1} + \sqrt{m^2-2} + \sqrt{m^2-3} + ... + \sqrt{m^2-(m^2-3)} + 1##
    Now how can we solve this equation
     
  5. Nov 18, 2014 #4

    rcgldr

    User Avatar
    Homework Helper

    Note that the floor of the square root is being used:

    T(n+1) = T(n) + ⌊ sqrt(n+1) ⌋
    T(1) = 1.

    I'm not sure how you convert this into a recursion tree, but note the pattern for fs(i) = ⌊ sqrt(i) ⌋ for i = 1 to 25:

    Code (Text):

    i     :  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
    fs(i) :  1  1  1  2  2  2  2  2  3  3  3  3  3  3  3  4  4  4  4  4  4  4  4  4  5
     
    There are three 1's, five 2's, seven 3's, nine 4's.

    Noting this pattern and converting into a sum for T(m^2) results in:

    T(m^2) = m + 1*0 + 3*1 + 5*2 + 7*3 + ... + (2m-1)(m-1)
    T(m^2) = m + sum i=1 to m: (2i - 1)(i - 1)

    Which is a cubic equation of the form:

    T(m^2) = a m^3 + b m^2 + c m + d

    You can calculate 4 sets of values for m and T(m^2) (m = 1, 2, 3, 4), then use linear algebra to solve for a, b, c, d. (In this case d is zero).

    Code (Text):

    |  1   1   1   1 |  | a |    |  1 |
    |  8   4   2   1 |  | b |    |  5 |
    | 27   9   3   1 |  | c | =  | 16 |
    | 64  16   4   1 |  | d |    | 38 |

    | a |   |  -1/6   3/6  -3/6   1/6 | |  1 |
    | b |   |   9/6 -24/6  21/6  -6/6 | |  5 |
    | c | = | -26/6  57/6 -42/6  11/6 | | 16 |
    | d |   |  24/6 -36/6  24/6  -6/6 | | 38 |

    | a |   |  4/6 |
    | b |   | -3/6 |
    | c | = |  5/6 |
    | d |   |  0/6 |
     
    T(m^2) = 4/6 m^3 - 3/6 m^2 + 5/6 m
     
    Last edited: Nov 18, 2014
  6. Nov 22, 2014 #5
    @rcgldr
    I agree with your approach, But please tell me how can we solve this equation

    ##T(m^2) = m + \sqrt{m^2 - 1} + \sqrt{m^2 - 2} + \sqrt{m^2 - 3} + ... + \sqrt{m^2 - {m^2 - 3}} + 1##
     
  7. Nov 23, 2014 #6

    rcgldr

    User Avatar
    Homework Helper

    I'm not sure it's possible without the integer floor function keeping the pattern simple. It's a non-linear recurrence equation. Link to wolfram example:

    http://www.wolframalpha.com/input/?i=sum+i+=+1+to+n,+sqrt(i)

    A linear recurrence equation has the form T(n) = a T(n-1) + b T(n-2) + c T(n-3) ... . For example the Fibonacci numbers are T(n) = T(n-1) + T(n-2), T(1) = 1, T(0) = 0. These can't be solved, but can be converted into a matrix form:

    Code (Text):

           | 1  1 |
       a = | 1  0 |

           | 1 |
    f(1) = | 0 |

    f(i+1) = a f(i)

    f(i+j) = a^j f(i)
     
    Powers of the matrix can be generated using repeated squaring: a^7 = (a * a^2 * a^4).
     
    Last edited: Nov 23, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to solve this recurrence
Loading...