If you’re looking to prove a statement of the form,
“For all positive integers \(n\), something is true,”
it’s sufficient to prove these two individual statements,
which are often each easier to prove:
-
“For \(n=1\) something is true.”
-
“If something is true for \(n=k\),
then something is true for \(n=k+1\) too.”
-
The country of Sectionia
uses a currency called silcrows, denoted \(\S\).
Curiously though, the Sectionian Mint
only prints \(\S 4\) and \(\S 5\) bills.
Although this seems rather limiting,
each Sectionian citizen, proud of their currency,
claims that they can pay
any whole \(\S\) amount of \(\S 12\) or greater
with some combination of these bills.
Is this true?
-
Find a formula in terms of \(n\)
for the maximum number of regions in which the plane
can be divided by \(n\) straight lines.
-
A typical chessboard is an \(8 \times 8\) grid of squares,
but let’s generalize this and refer to any \(m \times m\) square grid as a chessboard.
Say a chessboard is defective if one of its corner squares is missing.
Prove that for all \(n \gt 1\), any \(2^n \times 2^n\) defective chessboard
can be tiled—completely covered without overlapping—with L-shaped trominos
occupying exactly three squares.
Is it necessary to assume the missing square is a corner square?
-
Let \(r\) be a number such that \(r+\frac{1}{r}\) is an integer.
Prove that for every positive integer \(n\),
the number \(r^n+\frac{1}{r^n}\) is also an integer.
-
Putnam and Beyond
Prove that for any positive integer \(n\)
there exists an \(n\)-digit number that’s divisible by \(2^n\)
and contains only the digits “\(2\)” and “\(3\)”.
-
Putnam and Beyond
Prove that for any positive integer \(n\),
\[1 + \frac{1}{2^3} + \frac{1}{3^3} + \dotsb + \frac{1}{n^3} \lt \frac{3}{2}\,.\]
-
Prove that for every \(n \gt 2\),
the expansion of \((1+ x+ x^2)^n\)
contains at least one even coefficient.
-
Putnam and Beyond
Let \(x_1, x_2, \dotsc, x_n, y_1, y_2, \dotsc, y_m\)
be positive integers for \(n,m \gt 1\).
Suppose that
\[x_1 + x_2 + \dotsb + x_n = y_1 + y_2 + \dotsb + y_m \lt mn\,.\]
Prove that in the equality
\({x_1 + \dotsb} + x_n = {y_1 + \dotsb} + y_m \)
one can suppress some (but not all)
terms in such a way that the equality is still satisfied.
-
Prove that for every positive integer \(n\),
\[1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \dotsb + \frac{1}{\sqrt{n}}
\gt 2\Bigl(\sqrt{n+1}-1\Bigr)\,.\]
-
Show that every positive integer is a sum
of one or more numbers of the form \(2^r 3^s\),
where \(r\) and \(s\) are nonnegative integers
and no summand divides another.
(For example, 23 = 9 + 8 + 6.)
-
Let \(x_0,x_1,x_2,\dotsc\) be the sequence such that
\(x_0=1\) and for \(n \geq 0,\) \( x_{n+1} = \ln(e^{x_n} - x_n). \)
Show that the infinite series \( x_0 + x_1 + x_2 + \cdots \) converges and find its sum.