What Is the Solution to the Recurrence Relation T(m^2)?

[22990atinesh]

Homework Statement

If
$T(n+1)=T(n)+ \lfloor \sqrt{n+1} \rfloor , n \geq 1$
$T(1)=1$
then
$T(m^2) = ? , m \geq 1$

Homework Equations

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}$

 

[jedishrfu]

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

 

[22990atinesh]

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

 

[rcgldr]

Now how can we solve this equation

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:

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).

|  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

 

[22990atinesh]

@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$

 

[rcgldr]

tell me how can we solve this equation.

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:

       | 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).