Thread: Need help with proofs by induction

I am really stuck with a few problems and would really appreciate any assistance possible. The problems I am having trouble with are:

1. Prove: For every integer n greater than or equal to 1, 1 + (1/2) + (1/4) + ... + (1/(2^(n-1))) = (2^(n) - 1) / (2^(n-1))

2. Prove: For every integer n greater than or equal to 5, 2^n > 2n +1

3. Prove: For every integer n greater than or equal to 0, 5^n - 3^n is an even integer

4. Prove: For every line of people with a woman at the front and a man at the rear, there is always an instance in which a woman immediately precedes a man.

Again, any help that anyone could provide on how to answer these problems would be incredibly helpful.

let's look at number 4:

suppose we have a line of just two people: a woman at the front, and a man at the rear. then the woman immediately precedes the man (there's no one else in the line!).

now, suppose that we know that if the theorem was true for a line of n people, it was ALSO true for a line of n+1 people.

then true for a line of 2 people, would imply true for a line of 3 people, and true for a line of 3 people would imply true for a line of 4 people, and true for a line of 4 people....can you see where this is going?

so, let's assume this is true for a line of n people (with a woman in the front, and a man in the back). the only n we're sure this is true for at the moment is n = 2, but it might be true for some other n.

now suppose we have a line of n+1 people with a woman in the front, and a man in the back. so our line might look like:

W......MM (the last two people are men)
W......WM (the next to last person is a woman, and the last person is a man).

in the first case, then the first n people form a line with a woman in front, and a man in the back, and we are assuming that for this n (whatever it may be) we have some woman immediately in front of a man. well she's STILL immediately in front of that man if we just add one more man to the line.

in the second case, the next-to-last person in the line is a woman immediately in front of a man, so in this case we have a woman in front, a man in back, and some woman in front of a man.

so in ALL cases, whenever we have a line of n people with a woman in front and a man in back with a woman immediately in front of a man, a line of n+1 people with a woman in front and a man in back ALSO has some woman immediately in front of a man.

that is: the theorem true for n implies it is also true for n+1.

but we know it is true for n = 2, and thus true for n = 3, and then true for n = 4, and then true for n = 5...in short: true for any positive integer greater than or equal to 2.

let's look at how we go from n= 2 to n = 3 in greater detail:

here are the possible lines of length 2 that start with W and end with M:

WM

now, let's look at the possible lines of length 3 that start with W and end with M:

WMM <---already covered in the n = 2 case
WWM <--not covered by the n = 2 case, but true because it ends in WM

now let's look at lines of length 4:

WWMM <---covered in the case n = 3
WMMM <---covered in the case n = 3
WMWM <---not covered in the case n = 3, but ends in WM
WWWM <---not covered in the case n = 3, but ends in WM

rather than do an "infinite number" of proofs where we reduce the n+1 case to ether:

1) ends in WM
2) ends in MM (so that the n case applies)

we do "all of these proofs at once" (which is a LOT more efficient).

***********

let's look at how we can adapt this method to prove #2.

first we need to establish that 2⁵ > 2(5) + 1. since 32 > 11, this is indeed true.

now suppose that 2ⁿ > 2n + 1, for some (unspecified) n ≥ 5.

note that 2ⁿ⁺¹ = 2(2ⁿ) > 2(2n + 1) (by our assumption, above, that 2ⁿ > 2n + 1)

and 2(2n + 1) = 4n + 2. is this greater than 2(n+1) + 1 = 2n + 3?

well, n ≥ 5, so 2n ≥ 10 > 1.

hence 4n = 2n + 2n > 2n + 1, so 4n + 2 > 2n + 1 + 2 = 2n + 3.

thus 2ⁿ⁺¹ > 2(2n + 1) > 2n + 3 = 2(n+1) + 1.

that is, if 2ⁿ > 2n + 1, then 2ⁿ⁺¹ > 2(n+1) + 1, as well.

so true for n = 5, implies true for n = 6, implies true for n = 7, implies true for n = 8,......and so on: so true for ANY n ≥ 5.

(i don't know why you're being asked to prove this for n ≥ 5, it's clearly true for n ≥ 3).

**********

the idea is: to use the assumption of truth for n, to derive the (conditional) truth for n+1. if we can also find "a starting place" (some minimal n for which we know its true), then "the domino effect" takes place:

the proof for our "starting n" then proves true for n+1, and then n+1 proves the truth for n+2, and then n+2 proves the truth for n+3, and so on, for...well, forever.