Question #b936a

2 Answers
Jim H
Jan 13, 2018

I get #T(n) = 7^(log_2n)c+6(7^(log_2n)-4^(log_2n))#

Explanation:

Beginning with

#{(T(1) = c),(T(n)=7T(n/2)+(9n^2)/2) :}#.

We see that

#T(2) = 7T(2/2)+(9(2)^2)/2 = 7c+18#

When we look for #T(3)#, we get

#T(3) = 7T(3/2)+(9(3)^2)/2# but we don't have #T(3/2)#.

We can see that #T(4) = 7T(2)+(9(4)^2)/2# and the next value we can find using the given formula is #T(8) = 7T(4)+(9(8)^2)/2#

Motivated by the fact that we can find #T(n)# for #n =# a power of #2#, let's rewrite the problem.

Let #k = log_2n# so that #n=2^k# and

define #S(k) = T(2^k)#

Using the recurrence definition above, we have:

#S(0) = T(2^0) = T(1) = c#

#S(k) = T(2^k) #

# = 7T((2^k)/2) + 9/2(2^k)^2#

# = 7T(2^(k-1)) + 9/2(4^k)#

# = 7S(k-1) +9/2(4^k)#

Now we'll look for a pattern:

#S(0)=c#

#S(1) = 7S(0)+9/2(4^1)#

# = 7c+9/2(4^1)#

#S(2) = 7S(1) +9/2(4^2)#

# = 7(underbrace(7c+9/2(4^1))_(S(1)))+9/2(4^2)#

# = 7^2c+9/2(7 * 4^1) + 9/2(4^2)#

#S(3) = 7S(2) +9/2(4^3)#

# = 7(underbrace(7^2c+9/2(7 * 4^1) + 9/2(4^2))_(S(2)) )+9/2(4^3)#

# = 7^3c +9/2(7^2 * 4^1)+9/2(7 * 4^2) + 9/2(4^3)#

#S(4) = 7^4c +9/2(7^3 * 4^1) + 9/2(7^2*4^2)+9/2(7 * 4^3) + 9/2(4^4)#

In general we have

#S(k) = 7^kc+9/2sum_(i=1)^k(7^(k-i)4^i)#

I admit that I haven't worked out the sum myself, but my electronic helper says we get

# = 7^kc+9/2(underbrace(4/3(7^k-4^k))_"sum")#

So

#S(k) = 7^kc+6(7^k-4^k)#

Finally to return to the original problem replace #k# with #log_2n#

For #n = 2^k# we have #T(n) = S(k)#

Extend the domain to all #n > 0# by requiring the function to be continuous. We get

#T(n) = S(log_2n) = 7^(log_2n)c+6(7^(log_2n)-4^(log_2n))#

Note that #n^2 = (2^(log_2n))^2 = 4^(log_2n)# and we could regroup and factor to get

#T(n) = 7^(log_2n)(c+6)-6n^2#

Cesareo R.
Jan 14, 2018

See below.

Explanation:

Considering

#{(T_(1)=c),(T_(n)=aT_(n/2)+b n^2):}#

This is a linear non homogeneous difference equation so the solution can be posed as

#T_n = T_n^h+T_n^p# with

#T_n^h-aT_(n/2)^h=0# homogeneous and
#T_n^p-aT_(n/2)^p-bn^2=0# particular

Now considering the homogeneous solution

#T_n = C_0a^(phi(n))# and substituting we have

#a^(phi(n))-a^(phi(n/2)+1)=0 rArr phi(n)=phi(n/2)+1#

now making #phi(cdot) equiv log_2(cdot)# we have

#log_2(n) = log_2 (n/2) + 1# then the solution for #T_n^h# gives

#T_n^h=C_0 a^(log_2 n)#

Handling now the particular solution and making

#T_n^p= gamma n^2# we have

#gamma n^2-a gamma (n/2)^2 = b n^2# or

#gamma = (4b)/(4-a)# then

#T_n^p = (4b)/(4-a)n^2#

and then

#T_n = T_n^h + T_n ^p = C_0 a^(log_2 n) + (4 b)/(4-a)n^2#

now from the initial conditions

#T_1 = c = C_0+(4 b)/(4-a) rArr C_0 = c-(4 b)/(4-a)#

and finally

#T_n = (c-(4 b)/(4-a)) a^(log_2 n) + (4 b)/(4-a)n^2# or

#T_n = (c+6)7^(log_2 n)-6n^2#

Related questions
Impact of this question
779 views around the world
You can reuse this answer
Creative Commons License