Induction and Cardinality questions.

Question

I just had my exam today and I encountered some interesting problems that I need some help clarifying.

Question 1: If $n \in \mathbb{Z}$ Prove that $n^3<3^n$ for all of $n\ge 4$.

The method that I used to solve the above is induction:

Basis: Let $n = 4$, then $4^3 < 3^4$ is true.

Induction: We need to show that $n^3 < 3^n\implies (n+1)^3 < 3^{n+1}$

Assume that $n^3<3^n$, then we expand the consequent: $n^3 + 3n^2 + 3n + 1 < 3(3^n) = 3^n + 3^n + 3^n$

We have $n^3 < 3^n$, and since $n\ge 4$, then $3n^2 < 3^n$ and $3n < 3^n$.

Thus $n^3 < 3^n$.

This question is out of 8 marks, do you think that my answer is complete? Because the left side still has the " + 1 ", so I'm not sure if my method is correct.

Question 2: Prove that there "Do not" exist integers $k$ and $n$ such that $k^2 + 33 = 11^n$.

I tried to prove with contradiction method, however, it doesn't seem quite right:

Suppose there exist integers $k$ and $n$, then consider the following cases:

Case 1: Suppose $k$ and $n$ are both odd, then let $k = 2x + 1$ and $n = 2y + 1$, where $x,y$ are integers.

Then sub in for $k$ and $n$ in the equation we get $4^2 + 4k + 1 + 33$ is the sum of three even numbers, but $11$ to the power of any positive integers is odd, so it's a contradiction.

However, I'm stuck on the following case:

Case 2: Suppose $k$ and $n$ are both even, then let $k = 2x$ and $n = 2y$ where $x,y$ are integers.

Then sub the above into the equation we get $4k^2 + 33 = 11^n$, since $4k^2$ is even number, and $33$ is odd number, then even + odd = odd, since $11$ to the power of any positive integer is odd, then....the contradiction don't hold...

I guess my method is incorrect. But I really can't think of any other methods to solve this problem.

I will appreciate it very much if anyone can help me with these questions.

Thanks

Answer 1

You want to prove that $11^n-33$ is not a square (of integers).

Write $11^n-33 = x^2$ as $11\cdot(11^{n-1}-3)=x^2$. This shows that $11$ divides $x^2$ and hence $11$ divides $x$. On the other hand, the other factor, $11^{n-1}-3$ is surely not divisible by $11$. Altogether, no $x$ exists.

Answer 2

Q1

First point, it is better to show your calculations instead of just saying $4^3<3^4$.

Then there is an issue in you proof, you do not know that $3n^2<3^n$ nor $3n<3^n$, also where does the $+1$ went ?

---

Here is my wording proposal.

Let's prove by induction $P(n): n^3<3^n$ for some $n\ge n_0$.

$P(4)$ is true since $64=4^3 < 3^4=81$.

Let assume $P(n)$ and $n\ge 4$ then

$(n+1)^3 = n^3\times \left(\dfrac{n+1}{n}\right)^3 = \underbrace{n^3}_{<3^n\text{ by induction hypothesis}}\times\underbrace{\left(1+\dfrac 1n\right)^3}_{<3}<3^{n+1}$

Indeed since $n\ge 4$ then $(1+\frac 1n)^3<(1+\frac 14)^3=\dfrac{125}{64}<3$

So $P(n+1)$ is verified and we conclude that $P(n)$ is true for all $n\ge 4$.

Q2

Your idea of exploiting parity is fine, but you complicated uselessly.

Just say $11^n$ is always odd so $11^n-33$ is even.

For the equality to be verified we need $k$ to be even since $k$ and $k^2$ have the same parity.

However as you noticed we cannot progress further.

The idea by max zorn is a possibility, another possibility is to search contradictions with another modulo.

---

For instance let's examine the equation modulo $5$.

First let say that $n\ge 2$ else $k^2=11^n-33<0$ and this has no solution (this is to eliminate negative $n$'s).

$k^2+33\equiv 11^n\pmod 5\iff k^2+3\equiv 1\pmod 5\iff k^2\equiv 3\pmod 5$

$\begin{array}{|c|ccccc|}\hline x & 0 & 1 & 2 & 3 & 4\\\hline x^2 & 0 & 1 & 4 & 4 & 1\\\hline\end{array}\quad$ we see that it is not possible for a square to be $3$ modulo $5$

So the equation $k^2+33=11^n$ has no solution.