How to solve a recurrence relation to its closed form?

>>8437663
Since this is a multiple choice question, you can just test each one to see whether it satisfies the recurrence.

Also (2^m)^2 is 2^{2m}, not 2^{m^2}

And your second equation should be

T(2^{m-1})=T(2^{m-2})+2^(2*(m-1))

>>8437674
>Since this is a multiple choice question, you can just test each one to see whether it satisfies the recurrence.
True... but I actually want to learn something

hmm, how would I simplify, 2^m + 2^(2m - 2) + 2^(2m-4) . . . + 2^(0 - 2) ? Im not very good at maths. Would it be:

2^2m + 2^(2m -2) + 2^(2m-4) . . . .
factoring out 2^2m
2^2m(1 + 2^-2 + 2^-4 + 2^- 8 . . . (Idk what the last 2^(m-1)th term would be)

2^2m(1 + harmonic series??)

? lost idk how to get 4/3(n^2 - 1)

>>8437711
Yeah that's the right idea.
To figure out the last term, test a simple case like m=1. In this case, T(2^1)=T(1)+2^2.
Similarly, for m=2, T(2^2)=T(2)+2^{4}=T(1)+2^4+2^2. So your sum should stop at 2^2, not 2^(-2). And to get the answer just remember that n=2^m.

https://docs.google.com/a/dcp.org/forms/d/e/1FAIpQLScWPLAI4F05_h01lUcSTo6l4mqbcdmtw6Tb7a9Z3hdyrk_Dyg/viewform

take survey pls

https://docs.google.com/a/dcp.org/forms/d/e/1FAIpQLScWPLAI4F05_h01lUcSTo6l4mqbcdmtw6Tb7a9Z3hdyrk_Dyg/viewform

File: mein head2.png (322KB, 591x716px) Image search: [Google]

322KB, 591x716px

>>8437728
I dont know how to do it

>>8437757
Well you showed in the OP that
T(2^m)=T(2^0)+2^{2m}+2^{2m-2}+...+2^2=2^{2m}(1+2^{-2}+...+2^{2-2m}). =2^{2m}(1+(1/4)+...+(1/4)^{m-1}).

Now just use the formula for a finite geometric series and plug in n=2^m.

And next time post a question like this in the Stupid Questions thread (that's the name of an actual thread; not an insult)

>>8437778
I still dont get it

T(2^m) = T(2^(m-1) + 2^(2m)
T(2^(m-1)) = T(2^(m-2)) + 2^(2(m-1))
..
T(2^0) = 0

=> T(2^m) = 0 + 2^(2m) + 2^(2m-2) . . . 2^(1-1) <-- has m terms excluding the 0

=> T(2^m) = 2^(2m) [1 + 2^-1 + 2^-2+ 2^-3 . . . + 2^(m-1) ] + 2^0

=> T(2^m) = 2^(2m) * (1*(1-(1/2)^(m-2) ) ) / (1 - 0.5) + 2^0

u cant simplify this to get 4/3(n^2 -1) ?? how is this possible

>And next time post a question like this in the Stupid Questions thread (that's the name of an actual thread; not an insult)

ok sry i was desperate

>>8437813
Wtf im so close I keep getting

2^m * (1 - 4^(-1)^(m-1)) / 0.75
2^m * (1 - 4^(-m+1))/ 0.75
4/3 * 2^m - 2^m*4^(-m+1) but I cant simplify any further what am I dong wrong!!!

>>8437859
PLEASE

T(n) = 0 + (2^m + 2^(2m-2) + 2^(2m-6) + 2^(2m-8) . . . 2^(1-1) should consist of m terms right?

then T(n) = 2^m (1 + 2^-2 + 2^-6 + 2^-8 . . . 2^(m-1)) + 2^(1-1) should consist of m-1 terms!

Then why is 2^m * (1 - 4^(-1)(m-1))/ 0.75 not simplifying to answer B.) !!

THe simplest it goes to is 4/3 * (2^m - 2^(-m-2)) WTF?

>>8437887
????????????

File: 1477288693926.jpg (20KB, 292x326px) Image search: [Google]

20KB, 292x326px

>>8437663
>He doesn't know the master method

>>8437887
I get (4n^2-1)/3, which is close to B but not quite.

>>8438134
Nevermind, the sum was missing 1 at the end
T(2^m)=T(2^{m-1})+(2^m)^2
=T(2^{m-2})+2^{2(m-1)}^2+2^{2m}
=T(2^{m-3})+(2^2)^(m-2)+(2^2)^(m-1)+(2^2)^m
=T(2^{m-4})+4^(m-3)+4^(m-2)+4^(m-1)+4^m
continue this trend to
T(2^m)=T(2^{m-m})+4^{m-{m-1})+...+4^m
=T(1)+4+16+...+4^m
=G(4,m)-1 | G(n,m) is the geometric sum with argument n, and m terms.
=(1-4^{m+1})/(1-4)-1
=(4^(m+1)-1-3)/3
=(4^(m+1)-4)/3
=4(4^m-1)/3
=4/3({2^2}^m-1)
=4/3(2^(2m)-1)
=4/3({2^m}^2-1)
=4/3(n^2-1)