We define \(g: \mathbb{N}\rightarrow\mathbb{N}\) as follows:
Prove using strong induction that \(g(n) = 3 \cdot 2^n + (-1)^{n+1}\) for all natural numbers n.g(0) = 2
g(1) = 7
g(k) = g(k-1) + 2g(k-2), for \(k\ge 2\)
First, check your outline. Then fill in the inductive step and look at the full solution.
Stuck filling in the middle of the inductive step? Make sure that you've used the inductive hypothesis.
Use strong induction to prove De Moivre's Theorem, which states that the following holds for any real number x and any natural number n: $$(\cos x + i \sin x)^n = \cos(nx) + i \sin(nx)$$
where \(i = \sqrt{-1}\). Do this problem using high school trigonometry. Do not convert it to exponential notation and solve it that way.
Use strong induction to prove the following claim:
Claim: for any natural number \(n > 5\), a square can be cut up into n smaller squares (not necessarily all the same size).
First, experiment with dividing up a square, to understand why the claim is true. If you can't figure out informally how to divide up the square into different numbers of subsquares, see these hints.
Then try to write the proof. If you get stuck on that, here are more hints.
When you have a proof that seems close to correct, look at the solution.
Use strong induction to prove that the following holds for any positive integer n and any non-zero real number x.
If \(\displaystyle x + \frac{1}{x}\) is an integer then \(\displaystyle x^n + \frac{1}{x^n}\) is also an integer.
Outline the problem and fiddle with the equations for a bit. It's likely that you'll get stuck and eventually need to consult the hints. But you'll learn more if you first try to solve it on your own.
When you've got a full proof, check it against the solution.
To win the Monster Hunter game, you must defeat n monsters arranged along a circular path. The path also contains n energy cubes. To defeat each monster, you must first eat one energy cube. Prove that there is a place you can start on the circle which will allow you to win the game.
Use induction to prove the following claim:
For any graph G and any two nodes a and b in G, if there is a walk from a to b, then there is a path from a to b.In your proof, you should represent a walk from a to b as a sequence of nodes e.g. \(a=v_1, v_2, \ldots, v_n = b\).
A "triangle-free" graph is a graph that doesn't contain any 3-cycles. Use induction to prove the following claim:
For any positive integer n, a triangle-free graph with 2n nodes has \(\le n^2\) edges.
When you have a reasonable draft of a solution, look at the preliminary solution