prove by induction, not for natural numbers this time, but for real numbers

Question

Prove by induction: suppose there's a vertical column, infinitely tall from the ground. from 0 inches to 2 inches are dangerous zone, and up from 2 inches are safe zone. If you care climbing this column, you can jump up 1 inch for every move, but afterwards you will fall down to half of your vertical height. Prove that no matter how hight you starts, you will always fall into the dangerous zone in the end.

Answer 1

Divide the column into sections at height 0, 1, 2, 4, 8,... so that the first section is [0, 1) and the n'th section (n >1) is the height interval $[2^{n-2}$ to $2^{n-1})$.

Now propose the inductive hypothesis that starting in the N'th section the climber falls into the danger zone in at most 2N steps (in fact it will be less than 2N, but this works easily with an inductive proof).

The hypothesis is true for N=1 (he's at height < 1, so he's already in the zone in 0 steps), and for N=2 (he's at height < 2, so he's already in the zone in 0 steps). Now examine N > 2.

Assume true for sections up to and including N (i.e. he starts in or below section N) and consider what happens if he starts in section N+1. In his next move he attains a maximum height < $2^N + 1$ , and then immediately loses half his height: so his maximum height after this move is $2^{N-1} + 1/2$, which is in section N + 1 (since N > 2). And, a further move from here leaves him at a maximum height of $2^{N-2} + 3/4$, which is in section N. So after two moves he is at most in section N, and from there drops to the danger zone in at most 2N moves (by assumption), i.e. starting from section N+1 he drops in 2N + 2 = 2(N+1) moves.

So we have proved that he drops from section N to the danger zone in at most 2N moves, firstly showing this is true for N = 1, and then that if true for all n <= N then true for N + 1. This is an example of proof by "strong" or "complete" induction.

Note too, that we are not using induction of a range of "real" values, but on a range of discrete (countable) intervals.

Answer 2

Hint: Let $a_k$ be your height after $k$ jumps and falls (so each step consists of a jump and the subsequent fall). So $a_0$ is your starting height. Set up a recursion for $a_k$ for $k\ge 1$. Then prove that for any starting height $a_0$ the sequence $\{a_k\}_{k=0}^\infty$ is monotone and bounded (this is where you would do induction), and hence convergent. Then find the limit.