Suppose that $P(n_1, n_2, \ldots, n_N)$ be a proposition function involving $N >1$ positive integral variables $n_1, n_2, \ldots, n_N$. Then how to generalise the familiar induction to prove this statement?

Can the following possibly be correct?

(1) Suppose that $P(1, 1, \ldots, 1)$ is true.

(2) Suppose the truth of $P(k_1, k_2, \ldots, k_N)$ implies the truth of $P(k_1+1, k_2+1, \ldots, K_N+1)$.

Then $P(n_1, n_2, \ldots, n_N)$ is true for all $(n_1, n_2, \ldots, n_N) \in \mathbb{N}^N$.

For example, can we generalise induction to prove the following statement?

Let $m$ and $n$ be natural numbers such that $m < n$, and let $x$ be a real number such that $0 < x \leq \frac 1 2$. Then $$n^x - m^x < (n-m)x.$$

  • $\begingroup$ The proposed principle is not correct. The induction step would require (say for $2$ variable for brevity) that $P(x,y)$ implies $P(x+1,y)$ and $P(x,y+1)$. $\endgroup$ – André Nicolas Jun 2 '16 at 18:01
  • $\begingroup$ @AndréNicolas (using double induction) how to prove the truth or otherwise of the proposition at the very end of my post? $\endgroup$ – Saaqib Mahmood Jun 2 '16 at 21:04
  • $\begingroup$ Does it have to be double induction? Or induction at all? If any proof will do, then perhaps when I have the time I can write one out. $\endgroup$ – André Nicolas Jun 2 '16 at 21:10
  • $\begingroup$ @AndréNicolas any proof will do, but the one by induction will be highly appreciated. $\endgroup$ – Saaqib Mahmood Jun 2 '16 at 21:14

While this can indeed be done, your described approach certainly isn't enough - here's a counterexample! Let $P(x_1, . . . , x_n)$ be the statement $$"x_1=x_2=...=x_n."$$ Then $P(1, . . . , 1)$ is true, and $P(x_1, . . . , x_n)$ implies $P(x_1+1, . . . , x_n+1)$, but clearly $P$ is not true in general.

What's going on is that this scheme fails to take into account the fact that we need to allow the variables to increment independently. Based on this, can you see what type of statement you'll need to prove in general?

If you get stuck, you might also google the phrase "double induction" and see if you can generalize that to $n$-many parameters. But I suggest trying to figure it out yourself, first.

  • $\begingroup$ and what about the truth of the very last proposition? How to prove or disprove it? $\endgroup$ – Saaqib Mahmood Jun 2 '16 at 21:02

The question about generalized induction has been dealt with in the answer by Noah Schweber. Here is a quick non-induction proof of the desired inequality. Note that it works under conditions substantially more general than the conditions in the OP.

For fixed exponent $x$, consider the function $f(t)=t^x$. Then by the Mean Value Theorem we have $$\frac{f(n)-f(m)}{n-m}=f'(c)$$ for some $c$ between $m$ and $n$.

Note that $f'(t)=xt^{x-1}$, so $f'(c)=xc^{x-1}$. But since $x-1$ is negative and $c\gt 1$, we have $c^{x-1}\lt 1$, and therefore $xc^{x-1}\lt x$. This completes the proof.


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.