I am starting to finally understand mathematical induction but I am stuck on this problem.
After attempting it on my own, I got the following for the basis step:
n=1 so 1/2 <= 1 and that is true.
What I am really confused on is where to even begin for the induction step. I am having a really hard time grasping what I need to do. Any help is greatly appreciated.
After attempting it on my own, I got the following for the basis step:
n=1 so 1/2 <= 1 and that is true.
What I am really confused on is where to even begin for the induction step. I am having a really hard time grasping what I need to do. Any help is greatly appreciated.
-
This is a little bit of a tricky one! First, let's just see why it's true, maybe compute a few first cases:
n = 1: LHS = 1/2, RHS = 1/2
n = 2: LHS = 1/4, RHS = (1 * 3) / (2 * 4) = 1/4 * 3/2
n = 3: LHS = 1/6, RHS = (1 * 3 * 5) / (2 * 4 * 6) = 1/6 * 3/2 * 5/4
n = 4: LHS = 1/8, RHS = (1 * 3 * 5 * 7) / (2 * 4 * 6 * 8) = 1/8 * 3/2 * 5/4 * 7/6
Notice that, in each case, the RHS is simply the number we wanted, multiplied by a series of numbers that are slightly larger than 1. It should be clear now that this is true, since multiplication by each of these numbers increases magnitude. We just need to formalise this into an induction proof. We already have our basis step. Let's suppose that, for some k:
1 / (2k) <= [1 * 3 * ... * (2k - 1)] / [2 * 4 * ... * 2k]
Then:
1 / (2(k + 1)) = 1 / (2k) * (2k) / (2k + 2)
<= [1 * 3 * ... * (2k - 1)] / [2 * 4 * ... * 2k] * (2k) / (2k + 2) ... (by assumption)
<= [1 * 3 * ... * (2k - 1)] / [2 * 4 * ... * 2k] * (2k + 1) / (2k + 2)
= [1 * 3 * ... * (2k - 1) * (2k + 1)] / [2 * 4 * ... * 2k * (2k + 2)]
= [1 * 3 * ... * (2(k + 1) - 1)] / [2 * 4 * ... * 2(k + 1)]
as required. So, by induction it works for all n.
n = 1: LHS = 1/2, RHS = 1/2
n = 2: LHS = 1/4, RHS = (1 * 3) / (2 * 4) = 1/4 * 3/2
n = 3: LHS = 1/6, RHS = (1 * 3 * 5) / (2 * 4 * 6) = 1/6 * 3/2 * 5/4
n = 4: LHS = 1/8, RHS = (1 * 3 * 5 * 7) / (2 * 4 * 6 * 8) = 1/8 * 3/2 * 5/4 * 7/6
Notice that, in each case, the RHS is simply the number we wanted, multiplied by a series of numbers that are slightly larger than 1. It should be clear now that this is true, since multiplication by each of these numbers increases magnitude. We just need to formalise this into an induction proof. We already have our basis step. Let's suppose that, for some k:
1 / (2k) <= [1 * 3 * ... * (2k - 1)] / [2 * 4 * ... * 2k]
Then:
1 / (2(k + 1)) = 1 / (2k) * (2k) / (2k + 2)
<= [1 * 3 * ... * (2k - 1)] / [2 * 4 * ... * 2k] * (2k) / (2k + 2) ... (by assumption)
<= [1 * 3 * ... * (2k - 1)] / [2 * 4 * ... * 2k] * (2k + 1) / (2k + 2)
= [1 * 3 * ... * (2k - 1) * (2k + 1)] / [2 * 4 * ... * 2k * (2k + 2)]
= [1 * 3 * ... * (2(k + 1) - 1)] / [2 * 4 * ... * 2(k + 1)]
as required. So, by induction it works for all n.