Geometrical proof by induction

Question

Given a segment $AB$ of length $1$, define the set $M$ of points in the following way: it contains the two points $A,B$ and also all points obtained from $A,B$ iterating the following rule: for every pair of points $X,Y$ in $M$, the set $M$ also contains the point $Z$ of the segment $XY$ for which $YZ = 3XZ$. Prove by induction that the set $M$ consists of points $X$ from the segment $AB$ for which the distance from the point $A$ is either $$AX = \dfrac{3k}{4^n} \hspace{3 mm} \text{or} \hspace{3 mm}AX = \dfrac{3k-2}{4^n}$$ where $n,k$ are nonnegative integers.

I am confused by this question since I am not used to doing induction geometrically. Seeing as how we have to iterate each time a new point, I find it hard to formalize an inductive argument to prove this.

Answer 1

Every point on the segment $AB$ has some distance from $A$. So let's say you have two such points, $X$ and $Y$. Let $x$ denote the distance of $X$ from $A$, $y$ the distance of $Y$ from $A$.

Let $D$ be the set of distances from $A$ to each point in the set $M$ that is constructed in the problem. Recall the rule in the problem that says that if $X$ and $Y$ are members of the set $M$, the point $Z$ of the segment $XY$ for which $YZ = 3XZ$ is too. An equivalent rule is, if $x$ and $y$ are numbers in the set $D$, then the number $z$ between $x$ and $y$ such that $|z - y| = 3|z - x|$ also is in the set $D$.

The theorem you are to prove is that $D$ consists entirely of numbers of the form $\dfrac{3k}{4^n}$ or of the form $\dfrac{3k-2}{4^n}$.

There, now it's not a geometric induction any more. Just arithmetic.

There are still some complications, for example you can't just assume $x < y$, you can't just assume that one of $x$ and $y$ has the form $\dfrac{3k}{4^n}$ and the other has the form $\dfrac{3k-2}{4^n}$ (they might both have the same form), and you can't just use one value of $k$ to write both $x$ and $y$. You might have to consider several possible cases separately for the induction step.

Answer 2

Using the same starting point as David K to transform this into something more arithmetic, his expression

$|z - y| = 3|z - x|$

is equivalent to $z=\dfrac {3x}4 + \dfrac{y}{4} \quad\forall x ,y \in D$.

If $y>z>x$,then $|z - y| = 3|z - x|$ is equivalent to $y-z=3(z-x)$.

If, however, $x>z>y$, then $|z - y| = 3|z - x|$ is equivalent to $z-y=3(x-z)$. Both are equivalent statements. Solving for $z$,

$z-y=3(x-z)$

$z-y=3x-3z$

$4z=3x+y$

$z=\dfrac{3x}4+\dfrac y4$

$z$ will always take the form of $y$ (either $\dfrac{3k}{4^n}$ or $\dfrac{3k-2}{4^n}$). Modular arithmetic may ease explanation. The numerator is either 0 (first case) or 1 (second case) mod 3. $3x=0\mod 3$ so we need only consider how $y$ affects the form of $z$.

If $x$ and $y$ have the same denominator, then the numerator of $z$ is simply $3x+y$ and $(3x+y)\mod\ 3=y\mod\ 3$.

If the denominator of $y$ is greater than that of $x$, the numerator of $z$ is $(3x)(4^n)+y$ and $(3x)(4^n)+y\mod\ 3=y\mod\ 3$.

If the denominator of $x$ is greater than that of $y$, the numerator of $z$ is $3x+y(4^n)$. In modular arithmetic $(ab)\mod c=[(a\mod c)(b\mod c)]\mod c$. $4^n=1 \mod c \quad\forall n \in \mathbb{Z}$.
Therefore, $3x+y(4^n) \mod\ 3=y\mod\ 3$.