Proof by Induction
Maths and statistics discussion, revision, exam and homework help.
-
- Reputation:
- Thread Starter
- New Member
- Posts: 5
Proof by InductionHi, could someone please explain, in stages how to complete a question I have been trying to finish for a while, thanks.
I'm new to this and cannot insert pictures, sorry.
Sum of (from 1 to n) r[3^(r-1)]=¼[3^n(2n-1)+1]
Thanks.Last edited by helpstoask; 07-05-2012 at 16:18. -
- Reputation:
- TSR Demigod
- Posts: 5,512
Re: Proof by InductionYou need to show your working.(Original post by helpstoask)
Hi, could someone please explain, in stages how to complete a question I have been trying to finish for a while, thanks.
I'm new to this and cannot insert pictures, sorry.
Sum of (from 1 to n) r[3^(r-1)]=¼[3^n(2n-1)+1]
Thanks.
Inserting pictures isn't anything difficult, just upload the image on a image sharing site, and paste the link here. -
- PS Helper
- TSR Legend
Re: Proof by InductionAn outline of steps to get to the right answer will be:
Step 1: Show that it's true for
;
Step 2: Note that
and apply the induction hypothesis to the big bracket;
Step 3: Rearrange stuff.
If you're still stuck, show your working and we'll see where you're going wrong.
[For typing maths into TSR, look at the Guide to LaTeX.]Last edited by nuodai; 07-05-2012 at 16:30. -
- Reputation:
- TSR Demigod
- Posts: 5,512
Re: Proof by InductionThe OP has written the question as: Sum of (from 1 to n) r[3^(r-1)]=¼[3^n(2n-1)+1]:(Original post by nuodai)
An outline of steps to get to the right answer will be:
Step 1: Show that it's true for;
Step 2: Note that
and apply the induction hypothesis to the big bracket;
Step 3: Rearrange stuff.
If you're still stuck, show your working and we'll see where you're going wrong.
[For typing maths into TSR, look at the Guide to LaTeX.]
It means
-
- Reputation:
- Community Assistant
- TSR Royalty
- Location: Suffolk
- Posts: 18,170
Re: Proof by InductionHe has now but he hadn't then!(Original post by raheem94)
The OP has written the question as: Sum of (from 1 to n) r[3^(r-1)]=¼[3^n(2n-1)+1]:
It means
-
- PS Helper
- TSR Legend
Re: Proof by InductionThe OP edited their post whilst I was writing my reply. I'll edit my post appropriately - thanks.(Original post by raheem94)
The OP has written the question as: Sum of (from 1 to n) r[3^(r-1)]=¼[3^n(2n-1)+1]:
It means
-
- PS Helper
- TSR Legend
Re: Proof by InductionThere's actually a sneaky way to do this question.
Let
, then 
and so 
.
So extending this to the sum we have
![\displaystyle \sum_{r=1}^n r.3^{r-1} = \left[ \dfrac{d}{dx} \sum_{r=1}^n x^r \right]_{x=3}](http://www.thestudentroom.co.uk/latexrender/pictures/b7/b74034ce6dd17de5a1da4ecd20368c46.png "\displaystyle \sum_{r=1}^n r.3^{r-1} = \left[ \dfrac{d}{dx} \sum_{r=1}^n x^r \right]_{x=3}")
The sum in the brackets is a geometric series which evaluates to
, which differentiates (by the quotient rule) to give 
. Plugging in 
and simplifying gives the desired result.
[But you've been asked to prove this by induction.]Last edited by nuodai; 07-05-2012 at 16:41. -
- PS Helper
- TSR Legend
Re: Proof by InductionRight, so you have(Original post by helpstoask)
Still cannot, finish it, I don't know why, aiming for : ¼ [3^k+1 (2k+1) +1]
Sorry![\dfrac{1}{4}\big[3^k(2k-1)+ 1+4(k+1)3^k \big]](http://www.thestudentroom.co.uk/latexrender/pictures/c8/c8e80e5ff2f95b454269b59ff95de342.png "\dfrac{1}{4}\big[3^k(2k-1)+ 1+4(k+1)3^k \big]")
Take out the
as a common factor to get
![\dfrac{1}{4}\big[ 3^k[2k-1 + 4(k+1)] + 1\big]](http://www.thestudentroom.co.uk/latexrender/pictures/0d/0dec63733f12c6b55117b0ecf956a78a.png "\dfrac{1}{4}\big[ 3^k[2k-1 + 4(k+1)] + 1\big]")
Can you see what to do now, given what you've been told so far?
Hint: simplify the bracket after and then look for common factors.
Last edited by nuodai; 07-05-2012 at 16:51. -
- Reputation:
- Community Assistant
- TSR Royalty
- Location: Suffolk
- Posts: 18,170
Re: Proof by InductionThat's what you get if you follow my advice.(Original post by helpstoask)
Still cannot, finish it, I don't know why, aiming for : ¼ [3^k+1 (2k+1) +1]
Sorry -
- Reputation:
- Respected Member
- Posts: 194
Re: Proof by Inductionbut how do you factorise out the 3^k when there is a +1 in that first term?(Original post by nuodai)
You're close, you just need to simplify. The +1 is fine because that's in the final answer; so take out as a common factor from the other bits and see if you can rearrange to get the required form.
-
- Reputation:
- Community Assistant
- TSR Royalty
- Location: Suffolk
- Posts: 18,170
Re: Proof by InductionI suggested expanding it all for a reason, students with less ability than you struggle with anything but the simplest factorisation.(Original post by nuodai)
Right, so you have![\dfrac{1}{4}[3^k(2k-1)+1+4(k+1)3^k]](http://www.thestudentroom.co.uk/latexrender/pictures/99/99265cb7931ed0d16bd2f001f43abfa7.png "\dfrac{1}{4}[3^k(2k-1)+1+4(k+1)3^k]")
Take out the as a common factor to get
![\dfrac{1}{4}[3^k(2k-1 + 4(k+1)) + 1]](http://www.thestudentroom.co.uk/latexrender/pictures/30/30ef6d7a98baf46cd4a3c45bd79f5986.png "\dfrac{1}{4}[3^k(2k-1 + 4(k+1)) + 1]")
Can you see what to do now, given what you've been told so far?
Hint: simplify the bracket after and then look for common factors.
Last edited by Mr M; 07-05-2012 at 16:53. Reason: Point proved!
