1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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]$? $\endgroup$ – Rob Arthan Dec 12 '16 at 22:59
  • $\begingroup$ It would be infinite, correct? but I am not sure how to prove that either $\endgroup$ – Jotaro Dec 12 '16 at 23:00
  • $\begingroup$ 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? $\endgroup$ – Rob Arthan Dec 12 '16 at 23:20
  • $\begingroup$ 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? $\endgroup$ – Jotaro Dec 12 '16 at 23:45
  • $\begingroup$ 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 .... $\endgroup$ – Rob Arthan Dec 12 '16 at 23:49
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.