induction math problem
can anyone do this?
Prove by formal induction
a. 1 + 3 + 5 + ... + 2^n - 1 = n2, for n = 1, 2, 3 ....
prove it with a base case hypothesis and the last proof step
i forgot everything over break
dam i put this in the wrong section
January 19, 2013
8 Comments • Newest first
We didn't really do a lot of big O in my school. Only a few sorting/search algorithms..
[quote=supernoob]Np . Possiblyyy. Algorithms class... Computer Science?[/quote]
yessssssssss
time complexity big O notation wooooooooo
Np . Possiblyyy. Algorithms class... Computer Science?
[quote=supernoob]Base Case:
P_n 1 : 1 = 1
P_n 2 : 1 + 3 = 2^2 = 4
Inclusive Hypothesis: P_k 1 + 3 + 5 + ..... (2k - 1) = k^2
Prove: P_k+1 = 1 + 3 + 5 + ... (2(k + 1) - 1) = (k + 1)^2
And once you prove that, you're done.
Algorithms class? This is precalc.
Edit:
LHS = k^2 + 2(k + 1) - 1 = k^2 + 2k + 2 - 1 = k^2 + 2k + 1
RHS = (k + 1)^2 = k^2 + 2k +1[/quote]
your the best
and yes this is for my algorithms class lol I was suppose to know how to do this before I got into the class...
@Pendant: Well obviously our schools apportioned the topics for each subject differently, lol. In my school this was taught under precalc. Additionally, if you couldn't solve the problem, sthu .
Base Case:
P_n 1 : 1 = 1
P_n 2 : 1 + 3 = 2^2 = 4
Inclusive Hypothesis: P_k 1 + 3 + 5 + ..... (2k - 1) = k^2
Prove: P_k+1 = 1 + 3 + 5 + ... (2(k + 1) - 1) = (k + 1)^2
And once you prove that, you're done.
Algorithms class? This is precalc.
Edit:
LHS = k^2 + 2(k + 1) - 1 = k^2 + 2k + 2 - 1 = k^2 + 2k + 1
RHS = (k + 1)^2 = k^2 + 2k +1
Therefore, by the principle of mathematical induction, P_n holds true for any natural number n.
@makidua
[quote=Rtyu]What iz dis? You must be taking honors.[/quote]
lol this is from my algorithms class in college
its supposed to be a ez problem
solve it for me broseph
[quote=TaylorSwiftSuck]Fixed.[/quote]
your a boss
thanks for that
@Picklesandwich
noooooo i just want the answer I wouldnt be here if I wanted reteach myself