The Student Room Group

Proof by induction

Hi guys, new on tsr, just needed a little help on this proof by induction questions. Just started Further Maths as a year 12 student :smile:
Original post by kurmancii_
Hi guys, new on tsr, just needed a little help on this proof by induction questions. Just started Further Maths as a year 12 student :smile:


I suppose you did the base case?? Did you also write down the assumption?

By assumption, you know that r=1k(12)r=112k\displaystyle \sum_{r=1}^k \left( \dfrac{1}{2} \right)^r = 1-\dfrac{1}{2^k} so you can use this on your RHS.
Reply 2
Original post by RDKGames
I suppose you did the base case?? Did you also write down the assumption?

By assumption, you know that r=1k(12)r=112k\displaystyle \sum_{r=1}^k \left( \dfrac{1}{2} \right)^r = 1-\dfrac{1}{2^k} so you can use this on your RHS.


Yeah i did the basis step, and the assumption. so i got to this now but im so confused on what to do
Original post by kurmancii_
Yeah i did the basis step, and the assumption. so i got to this now but im so confused on what to do


You want to 'simplify' this expression and show that it is equal to 112k+11-\dfrac{1}{2^{k+1}}. I would begin by noting that 12k+1=1212k\dfrac{1}{2^{k+1}} = \dfrac{1}{2} \cdot \dfrac{1}{2^k}.

Remember, in the inductive step you wish to deduce that indeed we have r=1k+1(12)r=112k+1\displaystyle \sum_{r=1}^{k+1} \left( \dfrac{1}{2} \right)^r = 1-\dfrac{1}{2^{k+1}}
(edited 5 years ago)
Reply 4
Original post by RDKGames
You want to 'simplify' this expression and show that it is equal to 112k+11-\dfrac{1}{2^{k+1}}. I would begin by noting that 12k+1=1212k\dfrac{1}{2^{k+1}} = \dfrac{1}{2} \cdot \dfrac{1}{2^k}.

Remember, in the inductive step you wish to deduce that indeed we have r=1k+1(12)r=112k+1\displaystyle \sum_{r=1}^{k+1} \left( \dfrac{1}{2} \right)^r = 1-\dfrac{1}{2^{k+1}}


like this???
Original post by kurmancii_
like this???


Well, not what I was going for, but this is valid as well. Your first line is kinda pointless as it adds no value though.

Here you have just used the fact that 12k=222k=22k+1\dfrac{1}{2^k} = \dfrac{2}{2\cdot 2^k} = \dfrac{2}{2^{k+1}}

That said, you can combine the two fractions now quite easily since their denominators are the same.
Reply 6
Original post by RDKGames
Well, not what I was going for, but this is valid as well. Your first line is kinda pointless as it adds no value though.

Here you have just used the fact that 12k=222k=22k+1\dfrac{1}{2^k} = \dfrac{2}{2\cdot 2^k} = \dfrac{2}{2^{k+1}}

That said, you can combine the two fractions now quite easily since their denominators are the same.


Ok thank you so much, i added the two fractions. I checked the answer right now and it was right :smile: so what would you recommend i do for these types of questions? (like tips)

(I wrote my conclusion too btw)
Original post by kurmancii_
Ok thank you so much, i added the two fractions. I checked the answer right now and it was right :smile: so what would you recommend i do for these types of questions? (like tips)

(I wrote my conclusion too btw)


There isn't much specific advice to give because proof of induction ranges quite a bit depending on context, but in all cases, make sure you cover the base case, and write down the inductive hypothesis and box it, otherwise when it comes to working with the statement for n=k+1n=k+1, you get stuck because you forget about the inductive hypothesis and how useful it is for converting between different forms (like in this question, you converted from a summation to a nice single value). In every induction proof you must use the inductive hypothesis so it's important to retain it.
Once that has been applied, the rest is just knowing what you need to 'aim for' in a sense. So it would be also useful to write down the result you are 'aiming' to show before getting into it as it can act as a guide and prevent you from wondering down some horrible expressions.

Quick Reply

Latest