# Homework Help: How to solve this recurrence

Tags:
1. Nov 17, 2014

### 22990atinesh

1. The problem statement, all variables and given/known data
$T(n) = 2 T(n-1) + n, n \geq 2$
$T(1) = 1$
2. Relevant equations

3. The attempt at a solution
I'm using recursion tree method to solve the above recurrence

T(n) = Summation of non-leaf nodes + leaf nodes
$T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-1}$

2. Nov 17, 2014

### Staff: Mentor

3. Nov 17, 2014

### Staff: Mentor

4. Nov 17, 2014

### rcgldr

Each thread had a separate problem. Maybe they should have been combined.

T(n+1) = T(n) + floor(sqrt(n+1))
T(1) = 1.
(I assumed that ⌊ ⌋ meant the integer floor of the sqrt).

Note that floor(sqrt(1->3)) = 1, floor(sqrt(4 -> 8)) = 2, floor(sqrt(9->15)) = 3, ... .

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 (I'll let you solve this one):

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

I don't know if there's a more generic method to solve this.

- - -

T(n) = 2 T(n/2) + 2
T(1)=2
Code (Text):

n=2                               2
2             2

n=4                               2
2             2
2     2       2     2

n=8                               2
2             2
2     2       2     2
2 2   2 2     2 2   2 2

sum i=1 to log2(2n) : 2^i
2 T(n) - T(n) = T(n):

2 T(n) =        4 + 8 + 16 + ... + 2^(log2(2n)) + 2^(log2(4n))
T(n) =    2 + 4 + 8 + 16 + ... + 2^(log2(2n))
----------------------------------------
T(n) =   -2                                   + 2^(log2(4n))
T(n) =   -2                                   + 4n
T(n) = 4n - 2

- - -

For the summation series in the first post above, I used power series method, subracting 1 x series from 2 x series:

Code (Text):

2(T(n)) =        (2)(n  ) + (2^2)(n-1) + (2^3)(n-2) + ... + 2^(n-1)(2) + 2^(n)
T(n)  = (1)n + (2)(n-1) + (2^2)(n-2) + (2^3)(n-3) + ... + 2^(n-1)(1)
----------------------------------------------------------------------------
T(n)  =   -n + (2)      + (2^2)      + (2^3)            + 2^(n-1)    + 2^(n)

2(T(n)+n) =       (2^2) + (2^3) + ... + 2^(n-1) + 2^(n) + 2^(n+1)
T(n)+n  = (2) + (2^2) + (2^3) + ... + 2^(n-1) + 2^(n)
-----------------------------------------------------------------
T(n)+n  = -2                                          + 2^(n+1)

T(n) = 2^(n+1) - n - 2

Last edited: Nov 17, 2014
5. Nov 17, 2014

### Staff: Mentor

The other two copies have been deleted.

Edit: The other two copies were deleted in error. They have been reinstated.

Last edited: Nov 17, 2014
6. Nov 17, 2014

### 22990atinesh

as the height of the tree is n-1. So series would be
$T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-3}(n-[n-3]) + 2^{n-1}$
on solving with your approach I'm ending up with different ans
$2T(n) - T(n) = T(n) = n + 2 + 2^2 + 2^3 + ... + 2^{n-3} + 2{n-2}(n-[n-3]) + 2^{n-1} + 2$
$T(n) = n -1 - \frac{7}{2} 2^n$

7. Nov 17, 2014

### rcgldr

A terms is missing, it should be:

$T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-3}(3) + 2^{n-2}(2)+ 2^{n-1}$

Then 2 T(n) - T(n) is

$-n + 2 + 2^2 + 2^3 + ... + 2^n$

and you continue with T(n)+n as shown in my previous post.

8. Nov 18, 2014

### 22990atinesh

hmm Sorry little mistake

$T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-2}(n-[n-2]) + 2^{n-1}$
$2*T(n) = 2*n + 2^2(n-1) + 2^3(n-2) + ... + 2^{n-1}(n-[n-2]) + 2^{n}$

$2*T(n) - T(n) = - n + 2 + 2^2 + ... + 2^{n-2} + 2^{n-1} + 2^n$
$T(n) = - n + 2 + 2^2 + ... + 2^{n-2} + 2^{n-1} + 2^n + 2^0 - 2^0$
$T(n) = - n + 2^0 + 2^1 + 2^2 + ... + 2^{n-2} + 2^{n-1} + 2^n - 2^0$
Now We can directly apply sum of GP formula here

$T(n) = - n + \frac{2^{n+1} -1}{2-1} - 2^0$
$T(n) = 2^{n+1} - n - 2$

By the way what is this "Power Series Method". All I can find on internet is "Power Series Method" for differential equations.

9. Nov 18, 2014