6.7: Induction in geometry, combinatorics and number theory

Last updated
Save as PDF

Page ID: 81442

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

We turn next to a mixed collection of problems designed to highlight a range of applications.

Problem 256 Let $f_{1} = 2$ , $f_{k + 1} = f_{k} (f_{k} + 1)$ . Prove by induction that $f_{k}$ has at least k distinct prime factors.

Problem 257

(a) Prove by induction that n points on a straight line divide the line into $n + 1$ parts.

(b)(i) By experimenting with small values of n, guess a formula $R_{n}$ for the maximum number of regions which can be created in the plane by an array of n straight lines.

(ii) Prove by induction that n straight lines in the plane divide the plane into at most $R_{n}$ regions.

(c)(i) By experimenting with small values of n, guess a formula $S_{n}$ for the maximum number of regions which can be created in 3-dimensions by an array of n planes.

(ii) Prove by induction that n planes in 3-dimensions divide space into at most $S_{n}$ regions.

Problem 258 Given a square, prove that, for each $n \geq 6$ , the initial square can be cut into n squares (of possibly different sizes).

Problem 259 A tree is a connected graph, or network, consisting of vertices and edges, but with no cycles (or circuits). Prove that a tree with n vertices has exactly $n - 1$ edges.

The next problem concerns spherical polyhedra. A spherical polyhedron is a polyhedral surface in 3-dimensions, which can be inflated to form a sphere (where we assume that the faces and edges can stretch as required). For example, a cube is a spherical polyhedron; but the surface of a picture frame is not. A spherical polyhedron has

faces (flat 2-dimensional polygons, which can be stretched to take the form of a disc),
edges (1-dimensional line segments, where exactly two faces meet), and
vertices (0-dimensional points, where several faces and edges meet, in such a way that they form a single cycle around the vertex).

Each face must clearly have at least 3 edges; and there must be at least three edges and three faces meeting at each vertex.

If a spherical polyhedron has V vertices, E edges, and F faces, then the numbers V, E, F satisfy Euler's formula

$V - E + F = 2.$

For example, a cube has $V = 8$ vertices, $E = 12$ edges, and $F = 6$ faces, and $8 - 12 + 6 = 2$ .

Problem 260

(a) (i) Describe a spherical polyhedron with exactly 6 edges.

(ii) Describe a spherical polyhedron with exactly 8 edges.

(b) Prove that no spherical polyhedron can have exactly 7 edges.

Problem 261 A map is a (finite) collection of regions in the plane, each with a boundary, or border, that is `polygonal' in the sense that it consists of a single sequence of distinct vertices and – possibly curved – edges, that separates the plane into two parts, one of which is the polygonal region itself. A map can be properly coloured if each region can be assigned a colour so that each pair of neighbouring regions (sharing an edge) always receive different colours. Prove that the regions of such a map can be properly coloured with just two colours if and only if an even number of edges meet at each vertex.

Problem 262 (Gray codes) There are $2^{n}$ sequences of length n consisting of 0s and 1s. Prove that, for each $n \geq 2$ , these sequences can be arranged in a cyclic list such that any two neighbouring sequences (including the last and the first) differ in exactly one coordinate position.

Problem 263 (Calkin-Wilf tree) The binary tree in the plane has a distinguished vertex as `root', and is constructed inductively. The root is joined to two new vertices; and each new vertex is then joined to two further new vertices – with the construction process continuing for ever (Figure 11). Label the vertices of the binary tree with positive fractions as follows:

the root is given the label $\frac{1}{1}$
whenever we know the label $\frac{i}{j}$ of a ‘parent’ vertex, we label its `left descendant' as $\frac{i}{i + j}$ , and its `right descendant' $\frac{i + j}{j}$ .

(a) Prove that every positive rational $\frac{r}{s}$ occurs once and only once as a label, and that it occurs in its lowest terms.

(b) Prove that the labels are left-right symmetric in the sense that labels in corresponding left and right positions are reciprocals of each other.

Problem 264 A collection of n intervals on the x-axis is such that every pair of intervals have a point in common. Prove that all n intervals must then have at least one point in common.

Search

Text Color

Text Size

Margin Size

Font Type