Prove that if the irreducible rational fraction \(p/q\) is a root of the polynomial \(P (x)\) with integer coefficients, then \(P (x) = (qx - p) Q (x)\), where the polynomial \(Q (x)\) also has integer coefficients.
There are 8 glasses of water on the table. You are allowed to take any two of the glasses and make them have equal volumes of water (by pouring some water from one glass into the other). Prove that, by using such operations, you can eventually get all the glasses to contain equal volumes of water.
Theorem: All people have the same eye color.
"Proof" by induction: This is clearly true for one person.
Now, assume we have a finite set of people, denote them as \(a_1,\, a_2,\, ...,\,a_n\), and the inductive hypothesis is true for all smaller sets. Then if we leave aside the person \(a_1\), everyone else \(a_2,\, a_3,\,...,\,a_n\) has the same color of eyes and if we leave aside \(a_n\), then all \(a_1,\, a_2,\,a_3,...,\,a_{n-1}\) also have the same color of eyes. Thus any \(n\) people have the same color of eyes.
Find a mistake in this "proof".
Let’s look at triangular numbers, numbers which are a sum of the first \(n\) natural numbers: \[1+2+3+\dots +n\] Show using induction that the \(n\)-th triangular number is equal to \(\frac{n(n+1)}2\).
Show using induction that \(1+3+5+\dots+ (2n-1) = n^2\). That is, the sum of \(n\) first odd numbers is equal to \(n^2\).
Two convex polygons \(A_1A_2...A_n\) and \(B_1B_2...B_n\) have equal corresponding sides \(A_1A_2 = B_1B_2\), \(A_2A_3 = B_2B_3\), ... \(A_nA_1 = B_nB_1\). It is also known that \(n - 3\) angles of one polygons are equal to the corresponding angles of the other. Prove that the polygons \(A_1...A_n\) and \(B_1...B_n\) are congruent.
Show that \(2^{2n} - 1\) is always divisible by \(3\), if \(n\) is a positive natural number.
The famous Fibonacci sequence is a sequence of numbers, which starts
from two ones, and then each consecutive term is a sum of the previous
two. It describes many things in nature. In a symbolic form we can
write: \(F_0 = 1, F_1 = 1, F_n = F_{n-1} +
F_{n-2}\).
Show that \[F_0+F_1+ F_2 + \dots + F_n =
F_{n+2}-1\]
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\]