In a certain country, there are \(n\) cities. Some of them are connected by
roads, all of which go in both directions. It is possible to get from
any city to any other city using only roads. However, for any pair of
cities, there is always only one way to get from one of them to the
other and there are no alternative routes.
Show that there are exactly \(n-1\)
roads in this country.
If \(x\) is any positive real number and \(n \ge 2\) is a natural number, show that \[(1+x)^n > 1+nx\]
Anna and Bob play a game with the following rules: they both receive
a positive integer number. They do not know each other’s numbers, but
they do know that their numbers come one after another – they do not
know which one is larger. (If Anna gets \(n\), Bob gets either \(n-1\) or \(n+1\)). Anna then asks Bob – “do you know
what number I have?” If Bob does know, he has to say Anna’s number and
he wins the game. If he does not, he has to say that he does not. Then,
he asks Anna if she knows his number. If Anna does not know, she asks
Bob. This continues until one of them finds out what is the other’s
number. Assuming that both Anna and Bob know mathematics sufficiently
well to be able to solve this problem, find out who wins the game and
how.
For simplicity let’s assume Bob always gets the odd number and Anna
always gets the even number - two consecutive numbers have opposite
parity!
A real number \(y\) is such that \(y+\frac1{y}\) happens to be an integer. Show that for any natural \(n\), it is also true that \(y^n + \frac1{y^n}\) is an integer.
Show that if \(1+2+\dots+n = \frac{n(n+1)}{2}\), then \(1+2+\dots+(n+1) = \frac{(n+1)((n+1)+1)}{2}\).
Show that \(1+2+\dots+n = \frac{n(n+1)}{2}\) for every natural number \(n\).
Show that if \(1+2^1+2^2+\dots+2^{10} = 2^{11} - 1\), then \(1+2^1+2^2+\dots+2^{11} = 2^{12} - 1\).
Show that \(1+2^1+2^2+\dots+2^n = 2^{n+1} - 1\) for every natural number \(n\).
What is wrong with the following proof that “all rulers have the same length" using induction?
Base case: suppose that we have one ruler, then clearly it clearly has the same length as itself.
Assume that any \(n\) rulers have the same length for the induction hypothesis. If we have \(n+1\) rulers, the first \(n\) ruler have the same length by the induction hypothesis, and the last \(n\) rulers have the same length also by induction hypothesis. The last ruler has the same length as the middle \(n-1\) rulers, so it also has the same length as the first ruler. This means all \(n+1\) rulers have the same length.
By the principle of mathematical induction, all rulers have the same length.
Given a series of statements enumerated by the natural numbers, the strong induction principle says the following. Suppose that
The 1st statement is true (the base case).
Whenever all statements up to and including the \(n\)th statement is true, the \((n+1)\)th statement is also true (induction step).
Then the statement is true for all natural numbers. Show that the strong induction principle works.