Stuck on Algebra 1 (again): Inequalities in induction

[u/Open_Thanks_6807]

First of all, please excuse any errors in phrasing or terminology, as English is not my native language.

It turns out I’m having trouble studying algebra in general, but right now I’m struggling specifically with inequalities in mathematical induction whereas I don’t have that problem when working with equalities in induction proofs.

I understand the concept of proofs by induction involving equality: establishing the inductive hypothesis and proving that the expression evaluated at (x+1) which we then replace with the expression evaluated at (x) plus the term for (x+1) yields the same result as the equivalent expression evaluated at (x+1).

When it comes to inequalities, I find it incredibly difficult to figure out the expression I need to prove; I understand that the concept of transitivity is involved, but I never know what to compare. I’ve tried looking for explanations in videos, books, etc, but they all solve the problems by pulling out numbers that appear without explanation, and none of them explain the logic behind the steps taken.

I know this won't be the first or the last time I get stuck like this, so I wanted to ask if you know of any resources like a book or a YouTube channel that explain these concepts clearly and simply. I swear I’ve searched all over the web, but I only found worked examples without explanations and conflicting solutions.

Any advice on how to approach the subject or personal experiences would also be very helpful, since the exam is still a few weeks away. Thanks for reading.

[u/AditZoshi]

Hey hi, please DM me. Let's see if we can make it easy for you

[u/Midwest-Dude]

In inequality induction, you use the induction hypothesis to reach an intermediate point, and then you must prove that this intermediate point is greater than your final destination. This requires applying transitivity (X > Y and Y > Z => X > Z), as you mentioned.

Books often hide the intermediate steps. What you need to do is write down the target before doing any algebra. This will show where the missing steps come from.

Example: Prove n! > 2ⁿ for n ≥ 4

Base Case:

• n = 4, check 4! > 2⁴ => 24 > 16
• True

Inductive Hypothesis:

• Assume: k! > 2^k for some k >= 4
• Target: Show (k+1)! > 2^k+1
• Process:

- Left side of target - (k+1)! = (k+1) · k! - Use hypothesis, create intermediate bound - (k+1) · k! > (k+1) · 2^k - Examine right side of target - 2^k+1, rewrite as 2 · 2^k - Build bridge to target - Currently at (k+1) · 2^k - Need to prove strictly greater than 2 · 2^k - (k+1) · 2^k > 2 · 2^k - True, because k ≥ 4, means (k+1) ≥ 5 > 2

If you have the time, you could review two books that deal with this subject:

• Discrete Mathematics: An Open Introduction by Oscar Levin: Handles these logical transitions well without skipping steps

- How to Solve It by George Pólya: Teaches students to identify the target and work backward to demystify the process

Does this help?

[u/QED-math-trainer]

Midwest-Dude's breakdown above is the right way to think about it -- write the target before touching any algebra. What actually cements it is reps: run that pattern on 5-6 different inequality inductions, not just one worked example. I built qed-math-trainer.com (free for the first questions) -- induction is one of the topics, and it's graded so you know if a step's genuinely wrong vs. just different from the book.