I looked through my textbook trying to understand the concept but I am still clueless of how this works. Can someone please explain ?
Prove 2n+1 <= 2^n for all n>=3
Prove (1+x)^n >= 1+nx, where x>= -1
Mathematical induction can be tricky; it’s one of those things you only get a feel for after a lot of practice. I’ll do the first example to try to help show you the way.
First, we establish a base case. For n = 3, we see that 2 * 3 + 1 = 7, which is < 2^3 = 8, and so we know it’s true at that base point.
Now what we do is we assume that it’s true for an arbitrary value n = k. If we can prove that it being true for k implies that it’s true for k + 1, then we have an infinite chain from the base case: 3 implies that it’s true for 4, 4 implies that it’s true for 5, and so on.
Assume that (2k + 1) < 2^k. Then we’d like to show that:
2(k + 1) + 1 < 2^(k + 1)
Well, since 2k + 1 < 2^k, then:
2^(k + 1) > 2(2k + 1) (I just multiplied both sides by two), and so:
2^(k + 1) > 2k + 2 + 2k. But k > 3, so we know that:
2^(k + 1) > 2k + 2 + 2k > 2k + 3, and 2k + 3 = 2(k + 1) + 1
So by this chain of argument, 2^(k + 1) > 2(k + 1) + 1, and so we have that 2^k > (2k + 1) implies that 2^(k + 1) > 2(k + 1) + 1, and since we’ve established that this inequality holds for a base value 3, and since if it’s true for k, it’s true for k + 1, then it must be true for all integers larger than 3, and so we’re done.
Hope this helps!