Strong VS Weak Induction in Inequalities

[Mampac]

Hi there,

I'm entering the finals week and am doing some review questions.
I'm struggling with is induction which hasn't been tested during the semester therefore it's for sure going to be on the final, BUT...

One thing I can't understand is when to apply strong vs weak induction. There's no exact answer to this question on internet: they just say "Use strong induction when you don't have enough information to do the inductive step".... But how do I see whether I have enough information? I viewed a coupla examples of problems with strong induction and understood why the info wasn't enough there, but I'm sure that if I get a problem on it i won't be able to distinguish between them. Of course, I dropped by my professor's "zoom" office and she said that she can't give me a general pattern of characteristics than will help to identify a strong induction case. SO please help...

Another question that bothers me is proof by induction with inequalities. I can do equations myself, they're pretty easy, but you can't substitute things in inequalities, if you solve for a variable, right? I noticed they usually do... how's it called... estimations, like in Calculus? when you're sure that something is greater/less than something then you can just replace a whole hand-side with it.

In my case, it's 2^k ≤ 2^{k + 1} - 2^{k - 1} - 1
first, i wondered whether it's strong/weak and decided it's weak (correct me if i'm mistaken),
then in my inductive step, I wrote:
2^{k + 1} ≤ 2^{k + 2} - 2^k - 1
I separated 2's to get the inequality similar to my inductive hypothesis:
2^k × 2 ≤ 2^{k + 1} × 2 - 2^{k - 1} × 2 - 1
Now i get rid of 2's by dividing everything by 2:
2^k ≤ 2^{k + 1} - 2^{k - 1} - 1/2
Can i now do an estimation thingy and say that
2^k ≤ 2^{k + 1} - 2^{k - 1} - 1 < 2^{k + 1} - 2^{k - 1} - 1/2?
Is this gonna be it? Am i done? The strict inequality sign casts doubt though...

Thank you in advance! <3

 

[Steven G]

I am not sure what you mean by estimating? But i do know that if a < b then a < b + c whenever c>0. So yes, your proof is perfect. Good job.

Strong vs Weak induction: I guess you can try to think if it can be done with weak induction and if not then try strong induction. Personally I have never had a problem deciding. To be honest I almost always use weak induction.

You do know that you can always use strong induction. Then when it comes to prove the 'next case' then you only use what is needed.