# Have I used induction correctly in this proof of $x<y \implies x^n<y^n$?

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$.

• I think the proof is okay, I can't find anything wrong. – Anik Bhowmick Aug 8 '18 at 15:51
• probably $n\in \mathbb N$ in the claim – Exodd Aug 8 '18 at 15:51
• @Exodd I have made this change. – Benjamin Aug 8 '18 at 15:52
• @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. – Benjamin Aug 8 '18 at 15:53
• (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 ?? – Anik Bhowmick Aug 8 '18 at 15:59

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}$

• I am not sure I follow your superscript notation, could you possibly explain that in more detail? – Benjamin Aug 8 '18 at 15:54
• 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? – Cornman Aug 8 '18 at 15:55
• Yes that makes it clear, so long as by Inductive Claim you mean assuming $P(n)$ is true for $k$? – Benjamin Aug 8 '18 at 15:57
• 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. – Cornman Aug 8 '18 at 15:59

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$.
• Should I then have made more clear that because $x<y$ it is the case that $x^{n+1} < xy^n < y^{n+1}$? – Benjamin Aug 8 '18 at 15:56
• @Benjamin Yes, you should. – José Carlos Santos Aug 8 '18 at 15:57