Induction and Combinatorics

Using induction, prove that for natural $n$

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)$.

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

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

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

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 by $(*)$. 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-hand sides 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.

Find the error in the following ``proof by induction'' of the statement: in every herd of $n$ cows, all the animals are the same color.

Base case: if $n=1$, the herd consists of a single cow, so all the cows are the same color. Inductive step: suppose the statement has been proved for $n$. Consider a herd of $n+1>1$ cows. Remove a cow $x$ from this herd; by the induction hypothesis all the remaining $n$ cows are the same color. Remove a different cow $y$ from this herd; by the induction hypothesis all the remaining $n$ cows are again the same color. We then get that the colors of the cows $x$ and $y$ coincide with the colors of all the other cows, so all the cows in the herd are the same color.

The Fibonacci numbers $F_{i}, i \in \omega$, are defined as follows: $F_{i}=i$ for $i<2$, $F_{i}=F_{i-1}+F_{i-2}$ otherwise. Prove that $F_{i}$ is even if and only if $i$ is divisible by 3.

Prove the identity $F_{i-1} F_{i+1}=F_{i}^{2}+(-1)^{i}$ for the Fibonacci numbers, for $i>0$.

The number $e$ is the sum of the series $e=\sum_{i=0}^{\infty } 1 / i!$. Let $e_{n}$ be the sum of the first $n$ terms of this series: $e_{n}=\sum_{i<n} 1 / i!$. Prove that $A_{n}$ — the total number of arrangements without repetition of $n$ objects taken any number $m$ of places at a time — equals $e_{n} n!$. Conclude that for large $n$ it is approximately equal to $en!$.

Prove the identities:

Prove the binomial theorem using induction.

Prove that

where $\lfloor x\rfloor$ and $\lceil x\rceil$ denote rounding of the number $x$ down and up to the nearest integer, respectively.

Prove that the number of partitions of an $n$-element set into $k$ subsets, the first containing $n_{1}$ elements, the second $n_{2}$ elements, $\ldots$, the $k$-th $n_{k}$ elements, equals $\frac{n!}{n_{1}!n_{2}!\ldots n_{k}!}$.

A lecturer plans to teach the same course for 20 years. To avoid boring the students, he decided to tell them three jokes each year, with this set of three jokes never to be repeated. What is the minimum number of jokes he must prepare?

On an island there lives a tribe of natives whose mouths contain at most 30 teeth. No two inhabitants of the island have the same set of teeth (two sets are the same if, for every tooth, it is either present in both or absent in both). Could this island have more inhabitants than

Prove the Cauchy identity:

Prove that the number $C_{n}^{k}$ is odd if and only if $\rho (k) \subseteq \rho (n)$, where the value of the function $\rho (x)$ is the set of binary digit positions containing a 1 in the binary representation of the number $x$. In other words, if the binary representation of $k$ has a 1 in some position, then the binary representation of $n$ must also have a 1 in that position. Hint. Use induction on $n$, write $n=2^{u}+m$ for $1 \leqslant m \leqslant 2^{u}$, and apply the Cauchy identity.

A multiset is an unordered collection of elements in which each element may occur any number of times. Two multisets are equal if each element occurs in them the same number of times. For example, the multiset $\left\{ 1,2,1,3\right\}$ equals the multiset $\left\{ 3,1,1,2\right\}$ and does not equal the multiset $\left\{ 1,2,2,3\right\}$.

Prove that the number of ways to form a $k$-element multiset from $n$ pairwise distinct elements, using each of them any number of times, equals $C_{n+k-1}^{k}$.

A pastry shop sells four kinds of pastries: cream puffs, shortbread pastries, ``potato'' cakes, and sponge cakes. In how many ways can one buy

Let us call two outcomes of the Russian football championship coinciding in the essentials if in these outcomes the winners of the gold, silver, and bronze medals coincide, as well as the two teams relegated from the premier league (that is, that finished in the last two places). Find the number of distinct essentially-different outcomes (recall that 16 teams take part in the championship).

In how many ways can $n$ balls, of which $m$ are black and the rest white, be arranged in a row so that no two black balls end up adjacent?

Twelve knights sit at King Arthur's round table. Each of them is at odds with his neighbors. Five knights need to be chosen to free the princess. In how many ways can this be done so that no two chosen knights are enemies?

Solve this problem in the case where $k$ knights out of $n$ at the table need to be chosen.

Prove the inclusion-exclusion principle in set-theoretic form: if $A_{1}, \ldots , A_{n}$ are finite sets, then

How many of the first hundred positive natural numbers are not divisible by any of $2,3,5$? And among the first thousand numbers?

Determine how many integer solutions the following system has:

Find the number of permutations of $n$ elements in which no element remains in its original position.