0
$\begingroup$

So I wanted to prove this statement through Induction and I started as normal,proving that this statement is true for two random values of $n,p \in \mathbb{N} \space with\space p\geq 3$.

In the second step though I encounter a problem continuing this proof. I tried to conclude that if this statement is true for $n$ then it's also true for $n+1$ but none of my ideas to get there seem to work.

I am also hesitant about it only requering this step, and not also proving it for $p+1$

$\endgroup$
  • $\begingroup$ @lulu I want to prove that the inequality is true for the given set of natural numbers, and no, no given assumption regarding n and p, and that's a problem I encountered too $\endgroup$ – Konstantinos Zafeiris Nov 1 '17 at 21:07
  • 1
    $\begingroup$ So, first, I think it suffices to prove this for $p=3$, since for all $p>3$, we have $p^n>3^n$. Also, to prove $3^n>n^2$, if you start the inductive proof by $n=2$, then the inductive step from $n$ to $n+1$ should be straightforward $\endgroup$ – A. M. Nov 1 '17 at 21:11
  • $\begingroup$ This could be useful math.stackexchange.com/questions/2489665/… $\endgroup$ – rtybase Nov 1 '17 at 21:13
  • 1
    $\begingroup$ I have posted a non-inductive proof below. Of course, if the whole point was to prove the thing inductively, then this might not help much. $\endgroup$ – lulu Nov 1 '17 at 21:14
1
$\begingroup$

Base case: $p^1 > 1^2$. That's true as $p \ge 3$

Induction case: Assume we know $p^k > k^2$

Then $p^{k+1} = p*p^k > pk^2 \ge 3nk^2$

$= k^2 + 2k^2 = k^2 + 2k*k = k^2 +2k(k-1) + 2k = k^2 + 2k + 2k(k-1)$.

Hmmm, if $2k(k-1) \ge 1$ we would be done as that would mean $k^2 + 2k + 2k(k-1)\ge k^2 + 2k + 1 = (k+1)^2$.

But our base case was $n=1 $ and $2*1(1-1) =0$. So we need a second base case.

If $n=2$ then $p^2 > 2^3$ because $p \ge 3 > 2$.

So for $n \ge 2$ $2n(n-1) \ge 2*2*(2-1) = 4 > 1$.

So back to our induction step:

If $p^k > k^2$ and $k \ge 2$ then

$p^{k+1} \ge 3p^k > 3k^2 = k^2 + 2k + 2k(k-1) > k^2 + 2k + 1 = (k+1)^2$.

...

So we are done.

=======

We dont have to prove $P(p) \implies P(p+1)$ because there's nothing about it being true for $p+1$ that requires we know it is true for $p$ first. It's merely that if $p \ge 3$ it is true-- just because $p \ge 3$. We don't need to know it is true for $p-1$ first.

Example: You don't need to inductively prove that if $p \ge 17$ then $p$ is positive . $p \ge 17 > 0$ and we have no reason to have to prove it for $p-1$ first.

$\endgroup$
  • $\begingroup$ Completely answered both my questions. I also understood why sometimes the induction base case matters. Thank you $\endgroup$ – Konstantinos Zafeiris Nov 1 '17 at 21:35
1
$\begingroup$

If $p\geq 3$, then $p^n\geq 3^n$, for all $n\in\mathbb N$. Thus, it is enough to prove $3^n>n^2$. It is easy to verify that it holds for $n=1,2$.

Now, assume that the claim holds for $n\geq 2$. Then, we need to prove that

$$3^{n+1}> 3n^2 \geq (n+1)^2,$$

but, this easily follows from the fact that $2n^2-2n-1$ has roots $n_{1,2}=\frac{1\pm\sqrt 3}2$, so $3n^2\geq (n+1)^2$ for $n\geq 2 > \frac{1+\sqrt 3}2$.

$\endgroup$
0
$\begingroup$

Here is a non-inductive solution:

We consider the function $$f(x)=x^{2/x}$$ for $x≥1$

It is easy to differentiate this and thereby show that the unique maximum occurs at $x=e$. We then remark that $$f(e)\approx 2.087$$ In particular, $3>f(x)$ for all $x≥1$ and that suffices to prove your claim.

$\endgroup$
  • $\begingroup$ That's a solution to the problem, and one that I prefer too, but it's through differential calculus. I am searching for an approach to this through induction. $\endgroup$ – Konstantinos Zafeiris Nov 1 '17 at 21:14
  • $\begingroup$ Fair enough. I'll leave this up, as it does solve the problem, but I'll edit it to take note of the objection. $\endgroup$ – lulu Nov 1 '17 at 21:15
  • $\begingroup$ We can write: $3^{n+1}=3.3^n>3n^2$. Now, we need to show this to be greater than $(n+1)^2=n^2+2n+1$, or equivalently $2n^2>2n+1$, or $n^2>n+0.5$, and this is true for $n\geq 2$. $\endgroup$ – A. M. Nov 1 '17 at 21:18
  • $\begingroup$ @A.M. That's exactly the point that I am stuck $\endgroup$ – Konstantinos Zafeiris Nov 1 '17 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.