0

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.

infinityplus1
  • 25
  • You can try something on the line of "if, when you start from some height $h$ you reach the dangerous zone after $n$ jumps, then starting from $2h-1$..." –  Sep 15 '14 at 09:20
  • Can you specify what your inductive hypothesis and inductive steps are? Thanks. – infinityplus1 Sep 15 '14 at 09:38

2 Answers2

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.

Tom Collinge
  • 7,981
  • 25
  • 59
  • Thanks for pointing out that the induction is really over natural numbers (number of steps) after all. Height is a real-valued function of the number of steps, but the induction is not on height. – David K Sep 15 '14 at 13:28
  • Yes, induction doesn't work very well on real numbers. The above "strong" induction is applicable to any well ordered set (like the natural numbers or any subset of them), and in theory the reals can be well ordered but nobody has yet found such an ordering. – Tom Collinge Sep 15 '14 at 14:25
0

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.

paw88789
  • 40,402