Math Problems Vault

Problem 41

(a)(b)

Using induction, prove that

?

(a)

$2 n+1 \leqslant 2^{n}$ for $n \geqslant 3$ ;

(b)

$n^{2} \leqslant 2^{n}$ for $n \geqslant 4$ .

Problem 42

Using induction, prove that for natural $n$

?

(a)

$7^{n}-1$ is divisible by 6;

(b)

$11^{n}-6$ is divisible by 5;

(c)

$67^{n}-23^{n}$ is divisible by 4;

(d)

$3^{n}+7^{n}-2$ is divisible by 8;

(e)

$3^{n}+n^{2}$ is divisible by 4 for odd $n$ .

Problem 43

Prove that $1^{4}+2^{4}+\ldots +n^{4}=\frac{1}{30} n(n+1)(2 n+1)\left(3 n^{2}+3 n-1\right)$ .

?

Problem 44

Prove that $1 \cdot 2+2 \cdot 3+\ldots +n(n+1)=\frac{n(n+1)(n+2)}{3}$ .

?

Problem 45

Prove that $(1+2+3+\cdots +n)^{2}=1^{3}+2^{3}+3^{3}+\cdots +n^{3}$ .

?

Problem 46

Prove that

1 \cdot n+2 \cdot (n-1)+3 \cdot (n-2)+\cdots +n \cdot 1=\frac{n(n+1)(n+2)}{6}.

?

Problem 47

Prove that $1+x+x^{2}+x^{3}+\ldots +x^{n}=\frac{x^{n+1}-1}{x-1}$ for $x \neq 1$ .

?

Problem 48

Prove De Moivre's formula for natural powers of a complex number: if $z=r(\cos \varphi +i \sin \varphi )$ , then $z^{n}=r^{n}(\cos n \varphi +i \sin n \varphi )$ . Here $i$ is the imaginary unit, $i^{2}=-1, r$ and $\varphi$ are real numbers, $r \geqslant 0$ .

?

Problem 49

Prove that $n$ distinct lines in the plane divide it into regions, which can be colored white and black so that adjacent regions are colored with different colors.

?

Problem 50

Prove that $n$ distinct lines in the plane, no two of which are parallel and no three of which meet at one point, divide the plane into $\left(n^{2}+n+2\right) / 2$ regions.

?

Problem 51

Let in a convex $n$ -gon, $n \geqslant 4$ , no three diagonals meet at one point. Prove that it has $D(n)=\frac{(n-3)(n-2)(n-1) n}{24}$ points of intersection of diagonals.

?

Problem 52

Prove that if the cost of a certain letter is greater than or equal to 6 rubles, then it can be paid exactly using two- and seven-ruble stamps.

?

Problem 53

Find the error in the following "proof by induction" of the statement: for all $n \geqslant 1$ the inequality $3^{n}>3(n+1)+1$ holds.

Suppose that for some $k \geqslant 1$ the inequality holds, that is, $3^{k}>3(k+1)+1$ , denote this inequality (*). Let us prove that it also holds for $n=k+1$ , that is, $3^{k+1}>3(k+2)+1$ . To this end, note that for any $k \geqslant 1$ the inequality $2 \cdot 3^{k}>3$ holds. Adding its left and right side to the corresponding sides of inequality $(*)$ , we get $3^{k}+2 \cdot 3^{k}>3(k+1)+1+3$ or $3^{k+1}>3(k+2)+1$ , as required.

Determine for which $n$ the inequality $3^{n}>3(n+1)+1$ actually holds.

?

Problem 54

Find the error in the "proof by induction" of the following statement. Let $n$ circles in the plane be arranged so that any two of them have exactly two common points, and for any third circle $O$ one of these points lies inside $O$ and the other outside $O$ . Then the plane is divided by these circles into $N(n)=1+n(n-1)$ parts.

Base case: if $n=0$ , there is only one part. Step: suppose the statement holds for $n$ circles, $N(n)=1+n(n-1)$ . Then the $(n+1)$ -th circle has $2 n$ points of intersection with the previous ones (two with each). Hence it passes through $2 n$ regions and divides each of them into two. Therefore the number of regions increases by $2 n$ and we obtain $N(n+1)=N(n)+2 n=1+n(n-1)+2 n=1+(n+1) n$ .

Determine the actual value of $N(n)$ .

?

Problem 55

Let $n \geqslant 1$ spheres in space be arranged so that any three of them have exactly two common points, and for any fourth sphere $S$ one of these points lies inside $S$ and the other outside $S$ . Prove that space is divided by these spheres into $N(n)=2 n+\frac{n(n-1)(n-2)}{3}$ pieces.

?

Problem 56

Suppose that a certain colony of bacteria $\mathcal{C}$ consists of a finite number of individuals, for each of which a natural number is specified — the maximal number of divisions that the bacterium can survive, that is $\mathcal{C}=\left\{ (b, t): b \text{ — the bacterium's identifier, } t \text{ — the maximal number of divisions}\right\}$ .

At each step in the life of the colony one event occurs: some one bacterium $(b, t)$ is chosen and, if $t=0$ , it is removed from the colony ("dies"), and if $t>0$ , this bacterium is replaced by some finite set of bacteria ("divides"), where all its descendants are capable of dividing fewer than $t$ times.

Prove that any such colony $\mathcal{C}$ eventually becomes empty ("dies out"). Hint. Use induction on the maximal number of divisions $T: T=\max \left\{ t:(b, t) \in \mathcal{C}\right\}$ , and inside it, induction on the number of such bacteria.

?

Problem 57

The Fibonacci numbers are defined by the following recurrence relations: $F_{0}=0, F_{1}=1, F_{n+2}=F_{n+1}+F_{n}$ . Prove that

?

(a)

$F_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right] ;$

(b)

$F_{1}+F_{2}+F_{3}+\cdots +F_{n}=F_{n+2}-1$ ;

(c)

$n \cdot F_{1}+(n-1) \cdot F_{2}+(n-2) \cdot F_{3}+\cdots +1 \cdot F_{n}=F_{n+4}-n-3$ for $n \geqslant 1 ;$

(d)

$F_{n-1} F_{n+1}=F_{n}^{2}+(-1)^{n}$ for $n \geqslant 1$ ;

(e)

the numbers $F_{n}$ and $F_{n+1}$ are coprime for $n \geqslant 1$ ;

(f)

the number $F_{n}$ is even if and only if $n$ is divisible by 3;

(g)

$F_{n+m}=F_{n-1} F_{m}+F_{n} F_{m+1}$ for $n \geqslant 1$ .

Problem 58

Prove that for $n \geqslant 1$

\left[\begin{smallmatrix} 1 & 1 \\ 1 & 0 \end{smallmatrix}\right]^{n}=\left[\begin{smallmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{smallmatrix}\right].

?

Problem 59

Prove that there exist $F_{n+2}$ sequences of zeros and ones of length $n$ in which there are no two consecutive ones.

?

Problem 60

(a)(b)(c)

The Tower of Hanoi problem. There are three pegs. Several disks of decreasing diameter from bottom to top are placed on one of them (forming a children's pyramid toy). It is allowed to move the top disk from any peg to any other, but it is forbidden to place a disk of larger diameter on top of a disk of smaller diameter. The task is to move the entire pyramid to another peg.

?

(a)

Prove that $n$ disks can be moved in $2^{n}-1$ operations.

(b)

Prove that $n$ disks cannot be moved in fewer than $2^{n}-1$ operations.

(c)

Legend has it that at the beginning of time, in a temple in the city of Benares, the god Brahma created three pegs and placed 64 disks on one of them. Monks continuously move the disks from peg to peg according to the rules described above. When they move all the disks to another peg, the end of the world will come. Using the results of the previous parts, determine whether the end of the world should be expected in the near future.

Problem 61

The correctness of the Euclidean algorithm for finding the greatest common divisor of natural numbers is based on the following statement: $\gcd \left\{ x, y\right\} =\gcd \left\{ x-y, y\right\}$ for $y \leqslant x$ . Using this same statement, prove that there exist integers $a$ and $b$ such that $\gcd \left\{ x, y\right\} =a x+b y$ . Hint. Use induction on $x+y$ for a fixed $d=\gcd \left\{ x, y\right\}$ .

?