# Inductive proof of an infinite sequence

Consider a sequence bn (containing infinite amount of values) with values in ℝ, indexed by ℕ. Suppose the range of bn is contained in the finite interval [a, b].

Use the Principle of Mathematical Induction to prove that for any n ∈ ℕ, there is an interval of length (b-a)2n, k ≥ 1, which contains infinitely many terms of the sequence

I can understand it intuitively, bn has infinite terms, so there exists a subset of bn that also has infinite terms. However, I am not sure how I would go about predicting this inductively.

• Hint: if $[x, y]$ contains infinitely many $b_n$, what can you say about (at least one of) $[x, z]$ and $[z, y]$ where $z = (x+y)/2$ is the midpoint of $[x, y]$? – Rob Arthan Dec 12 '16 at 22:59
• It would be infinite, correct? but I am not sure how to prove that either – Jotaro Dec 12 '16 at 23:00
• Well what can you say if both $[x, z]$ and $z, y]$ contained only finitely many $b_n$? Could there be infinitely many distinct $b_n$ in that case? – Rob Arthan Dec 12 '16 at 23:20
• I'm not sure what you mean by that. Are you saying if b<sub>n</sub> had a finite number of elements? In that scenario wouldn't both intervals also have a finite number of elements? – Jotaro Dec 12 '16 at 23:45
• I am asking you to think about what will be the induction step in your proof. You'll have an inductive hypothesis that an interval $[x, y]$ contains infinitely many of the $b_n$ and you'll need to come up with an interval with length $(x-y)/2$ which also contains infinitely many of the $b_n$. Over to you .... – Rob Arthan Dec 12 '16 at 23:49

Base case $n = 0$

The interval $(a,b)$ has infinitely many members of $\{b_n\}$.

Inductive hypothesis:

Suppose there is an interval of lenght $\frac {(b-a)}{2^n}$ that contains infinitely many points. Lets call this interval $(c,d)$

We must show that if when the hypothesis is true it implies that there is an interval of length $\frac {(b-a)}{2^{n+1}}$ that contains infinitely many points.

$(c, \frac {c+d}{2})$ and $(\frac {c+d}{2}, d)$ are sub-intervals of (c,d) each or length $\frac {(b-a)}{2^{n+1}}$

At least one of $(c, \frac {c+d}{2})$ and $(\frac {c+d}{2}, d)$ has infinitely many points. i.e. if neither do, then $(c,d)$ does not have infinitely many points, and that would contradict our assumption.

QED