2
$\begingroup$

A while ago I posted an attempt at a proof of $x<y \iff x^n<y^n$. It was pointed out that I hadn't actually used induction, and had instead done a direct proof. Below is the link to the question, so please do not mark this question as a duplicate, as this new question is about whether I have now done the proof by induction correctly, rather than accidentally reverting to a direct proof.

Is this proof of $x<y \iff x^n < y^n$ correct?

Also, be aware that I am, below, attempting to prove only that $x<y \implies x^n<y^n$.

Claim: $x<y \implies x^n<y^n$ for $x,y>0$ and $x,y,n \in \mathbb N$.

Proof:

Let $P(n)$ be the statement that $$x<y \implies x^n<y^n,$$ for $n\in \mathbb N$. It is clear that $P(n)$ holds for $n=1$ since $x<y \implies x<y$.

Assuming that $P(n)$ holds for some $n = k$, we see that this implies that $P(n)$ holds for $n=k+1$, as follows.

$$x<y \implies x^n<y^n$$

Since we know that $x<y$, if we multiply $x^n<y^n$ by $x$ we get that: $$x^{n+1} < xy^n,$$ from which it follows that $$x^{n+1} < y^{n+1}.$$

Thus $P(k)$ true $\implies$ $P(k+1)$ true, and so by induction we can prove the claim that $P(n)$ holds for all $n \in \mathbb N$.

$\endgroup$
5
  • 1
    $\begingroup$ I think the proof is okay, I can't find anything wrong. $\endgroup$ – Anik Bhowmick Aug 8 '18 at 15:51
  • 1
    $\begingroup$ probably $n\in \mathbb N$ in the claim $\endgroup$ – Exodd Aug 8 '18 at 15:51
  • $\begingroup$ @Exodd I have made this change. $\endgroup$ – Benjamin Aug 8 '18 at 15:52
  • $\begingroup$ @AnikBhowmick I feel a bit uncomfortable with the step where I multiply by $x$, since I (a) feel like I am ignoring the LHS and (b) am not sure how this exactly relies on the fact that P(n) is true. $\endgroup$ – Benjamin Aug 8 '18 at 15:53
  • 1
    $\begingroup$ (a) Since $x>0$, it's completely okay. There is no fact of ignoring the LHS. (b) That's the statement of mathematical induction, right ?? If $P(K+1)$ is true whenever $P(K)$ is true, then $P(n)$ is true $\forall n \in \mathbb N$ !! Where is the ambiguity ?? $\endgroup$ – Anik Bhowmick Aug 8 '18 at 15:59
1
$\begingroup$

In my opinion you should work better out where and how you use the inductive claim (I. C.).

$x^{n+1}=x\cdot x^n\stackrel{I.C}{<}x\cdot y^n\stackrel{x<y}{<}y\cdot y^n=y^{n+1}$

$\endgroup$
4
  • $\begingroup$ I am not sure I follow your superscript notation, could you possibly explain that in more detail? $\endgroup$ – Benjamin Aug 8 '18 at 15:54
  • $\begingroup$ Sure: The superscript $I.C$ notes, that this estimation uses the inductive claim. The superscript $x<y$ notes, that we use for this estimation, that $x<y$ by assumption. Is it clear now? $\endgroup$ – Cornman Aug 8 '18 at 15:55
  • $\begingroup$ Yes that makes it clear, so long as by Inductive Claim you mean assuming $P(n)$ is true for $k$? $\endgroup$ – Benjamin Aug 8 '18 at 15:57
  • 1
    $\begingroup$ The inductive claim $P(n)$ is, that the estimation $x^n<y^n$ holds for arbitrary (but fixed) $n\in\mathbb{N}$. You do not need to involve $k$, as José Carlos Santos pointed out. $\endgroup$ – Cornman Aug 8 '18 at 15:59
2
$\begingroup$

It is correct. Two remarks, though:

  1. There is no need to use two letters ($n$ and $k$). One is enough.
  2. Indeed, it follows from $x^{n+1}<xy^n$ that $x^{n+1}<y^{n+1}$, but you did not say why. This is where you use the fact that $x<y$.
$\endgroup$
2
  • 1
    $\begingroup$ Should I then have made more clear that because $x<y$ it is the case that $x^{n+1} < xy^n < y^{n+1}$? $\endgroup$ – Benjamin Aug 8 '18 at 15:56
  • $\begingroup$ @Benjamin Yes, you should. $\endgroup$ – José Carlos Santos Aug 8 '18 at 15:57

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.