Help wirh mathematical induction (1 Viewer)

[littlesmallworld]

Prove for all integers n in
1+3+3^2+3^3+..+3^(n-1) = (3^n -1)/2

 

[HSC2014]

What part did you need help with? Do you understand the idea/logic behind proof by induction?

 

[Drongoski]

1 = (3^1 -1)/2

.: true for n = 1

Assume true for n=k >= 1

i.e. 1 + 3^1 + 3^2 + . . . + 3^(k-1) = (3^k -1)/2

.: 1 + 3 + . . . + 3^(k-1) + 3^k = (3^k -1)/2 + 3^k = (3^k - 1 + 2 x 3^k)/2 = (3 x 3^k - 1)/2 = (3^(k+1) -1)/2

i.e. if formula holds for n = k, it holds for n = k+1

.: by Mathematical Induction, formula holds for all integers n >= 1.

 

[obliviousninja]

4 steps (making sure you stay within your number set where stated: e.g. all positive integers):

1. Prove for n = 1

2. Assume result is true for n=k

3. We want to show the k+1 term also follows the result. To do this we show that S[k+1] = S[k] + T[k+1]

So here you sub in k+1 to the sum, simplify. This is the LHS. Now sub in k to S, and k+1 to the nth term - this is the RHS. Now that this is done, show RHS = LHS, or LHS = RHS. Simplify and manipulate S[k] +T[k+1] until it equals S[k+1]. This can be tricky, but it is usually not too difficult.

4. Statement of mathematical induction

Not to be rude, but that doesn't really help. You are just outlining the general method, not focusing on the specificity of the question at hand

 

[HSC2014]

Cmon guys Induction is beautiful, wouldn't you rather enlighten someone on the topic than just feed the answer. That is only helpful short term.

 

[RealiseNothing]

That's a pretty stupid induction.

 

[asianese]

Well, sure, the formula for a geometric series can be applied...but I think its just to confirm it using another method.

 

[Drongoski]

Mr Pappa

I like your outline; spells out the steps very nicely.

 

[RealiseNothing]

Well, sure, the formula for a geometric series can be applied...but I think its just to confirm it using another method.

It would make a student think induction is pointless though.

 

[hit patel]

Can you do it this way guys:?

Let n=1
LHS=3^(1-1)=1
RHS=(3^1-1)/2 = 1 First we prove that it is true by letting n=1 where RHS has to equal LHS then its true.
Therefore true for n=1

Assume 1+3+3^2+3^3+....+3^(n-1)=3^(n-1)/2 -------------1)
RTP: 1 + 3+3^2+3^3 +.... + 3^(n-1)+3^n= (3^n)/2 ----2)Now we assume that LHS = RHS and therefore n+1 should give the results of LHS=RHS

LHS= 3^(n-1)/2 + 3^n ----- From 1) and 2)

Then simplify to get RHS. ( sorry i didnt as Iwas told- not to give the answer)

Then statement : This is true by PMI

Did I do anything wrong ?

 

[SpiralFlex]

Can you do it this way guys:?

Let n=1
LHS=3^(1-1)=1
RHS=(3^1-1)/2 = 1 First we prove that it is true by letting n=1 where RHS has to equal LHS then its true.
Therefore true for n=1

Assume 1+3+3^2+3^3+....+3^(n-1)=3^(n-1)/2 -------------1)
RTP: 1 + 3+3^2+3^3 +.... + 3^(n-1)+3^n= (3^n)/2 ----2)Now we assume that LHS = RHS and therefore n+1 should give the results of LHS=RHS

LHS= 3^(n-1)/2 + 3^n ----- From 1) and 2)

Then simplify to get RHS. ( sorry i didnt as Iwas told- not to give the answer)

Then statement : This is true by PMI

Did I do anything wrong ?

You what? What does LHS = RHS mean in that context? Make sure you are clear on each step.


























<------State your intentions






<------Must state how you go LHS to RHS.

 

[hit patel]

I wrote the LHS=RHS to show him steps. It was not actually in the working. Sorry if you misunderstood. Its really hard to understand the questions without latex. I did a mistake by misinterpreting the question:

Mistake Here: Assume 1+3+3^2+3^3+....+3^(n-1)=3^(n-1)/2 -------------1)

Correct should be ôn the RHS: (3^n -1)/2

 

[hit patel]

Also does anyone have good and challenging Induction Questions including Product type, division type inequality type and addition type? Please post them if possible.
Thank you.

 

[SpiralFlex]

Also does anyone have good and challenging Induction Questions including Product type, division type inequality type and addition type? Please post them if possible.
Thank you.

Yup, but not your usual standard induction equations for 3U

http://www-history.mcs.st-and.ac.uk/~john/MISS.pdf

http://www.geometer.org/mathcircles/indprobs.pdf

 

[hit patel]

WEll just one more question that puzzles me:

2+4+6+....+2n= n(n+1) Here we consider a series where in RTP we need: 2n + (2n+1) + 2(n+1)

However here :
1^2+3^2 + ^2+...+(2n-1)^2 = n(4n^2 -1)/3

In RTP here we donot consider that method: we donot say (2n-1)^2+(2n)^2+(2n+1)^2
But INstead we say (2n-1)^2+(2n+1)^2. Why does this happen? please explain.

Thanks for the resources but are they in the NSW syllabus?
Cheers

 

[SpiralFlex]

WEll just one more question that puzzles me:

2+4+6+....+2n= n(n+1) Here we consider a series where in RTP we need: 2n + (2n+1) + 2(n+1)

However here :
1^2+3^2 + ^2+...+(2n-1)^2 = n(4n^2 -1)/3

In RTP here we donot consider that method: we donot say (2n-1)^2+(2n)^2+(2n+1)^2
But INstead we say (2n-1)^2+(2n+1)^2. Why does this happen? please explain.

Thanks for the resources but are they in the NSW syllabus?
Cheers

I don't understand what you are trying to say sorry but for your first question:

We require to prove (for the appropriate values of k)



If you have difficulties with that, try equivalently proving:



For your second question:

 

[hit patel]

But spiral for the fiirst question according to textbook we are required to prove : 2+4+6+.....+2k+ (2k+1) + 2(k+1) = (k+1)((k+1)+1)

However for the second question you and I am right.

 

[HeroicPandas]

Yup, but not your usual standard induction equations for 3U

http://www-history.mcs.st-and.ac.uk/~john/MISS.pdf

http://www.geometer.org/mathcircles/indprobs.pdf

Noice! Thanks for sharing!

 

[HAX0R]

Prove it for n=1.
Assume it is true.
Prove it for k+1.
Therefore, it is true for n.

 

[littlesmallworld]

Hi, im dont understand this bit
(3^k - 1 + 2 x 3^k)/2 = (3 x 3^k - 1)/2
Can u elaborate??
But thanks for the help