Hint: \((n+1)^{n+1} > (n+1) \cdot n^{n}\text{.}\)
Hint: This should be similar to the other sum proofs. The last bit comes down to adding fractions.
Hint: Write \(4^{k+1} - 1 = 4\cdot 4^k - 4 + 3\text{.}\)
Hint: one 9-cent stamp is 1 more than two 4-cent stamps, and seven 4-cent stamps is 1 more than three 9-cent stamps.
Careful to actually use induction here. The base case: \(2^2 = 4\text{.}\) The inductive case: assume \((2n)^2\) is divisible by 4 and consider \((2n+2)^2 = (2n)^2 + 4n + 4\text{.}\) This is divisible by 4 because \(4n +4\) clearly is, and by our inductive hypothesis, so is \((2n)^2\text{.}\)