2
$\begingroup$

Suppose I have a conjecture of the form $\forall x \in \mathbb{N}^{+}$ $f(x) > g(x)$.

Without explicitly giving the functions $f$ and $g$ I would like to prove this conjecture using induction.

Specifically I have shown $f(1) > g(1)$. My inductive assumption is now that $f(x - 1) > g(x - 1)$ and I'm trying to show $f(x) > g(x)$.

I haven't been able to do this, but I've noticed that I can if I assume $f(y) > g(y)$ $\forall y \in \mathbb{N}^{+}$ such that $y < x$ instead of my inductive argument I can prove $f(x) > g(x)$.

My question is, is this ok or am I using circular logic? Typically when we use induction we use $x - 1$ to prove the $x$ case after an initial base case. For my problem it doesn't appear possible to prove $f(x) > g(x)$ without assuming that for all values less than $x$ the conjecture holds ($f$ and $g$ are recursive). I suspect that it is ok, but it sounds extremely circular and I haven't been able to convince myself that it isn't.

Note also that I've included proof verification as a tag because although I have not included the explicit proof, I have included a proof approach that I'm interested in validating.

$\endgroup$
  • $\begingroup$ That's fine. That's called strong induction. It might be clearer if worded it slightly differently. You know $f(1) > g(1)$ and you have proven that if $f(y)> g(y)$ for all $y \le x-1< x$ then $f(x) > f(x)$. Hence... induction. Is that clearer? $\endgroup$ – fleablood Oct 14 '17 at 17:13
1
$\begingroup$

So you just want to make the stronger assumption that some statement $P(y)$ holds for all $y < x$ instead of only for $y = x-1$?

This is totally fine. It is called strong induction and is equivalent to simple induction.

$\endgroup$
  • 1
    $\begingroup$ Ok, that's what I thought. I was just a bit unsure because I couldn't remember doing something like this in any course I've taken. Thank you! $\endgroup$ – HXSP1947 Oct 7 '17 at 1:54
1
$\begingroup$

"Typically when we use induction we use x−1 to prove the x case after an initial base case. For my problem it doesn't appear possible to prove .. the proposition.. without assuming that for all values less than x the conjecture holds"

Think about this. If being true for all $y \le x-1 < x \implies $ being true for $x$, then being true for $y < x$ and being true for $x$ implies being true for all $y < x+1$. So true for $x+1$. And so on.

In principal, this is the exact same reasoning as the reasoning for induction. (if it's true for one case, it's true for the next, and via infinite countable reptitions it must be true for all).

The only difference is that whereas in "weak" induction we only make use of the fact that the proposition is true of $1$ and for $x-1$ and therefore true for $x$ we don't need to and we don't make use of the fact that it must also be true for $1,.......,x-2$ as well as just $x-1$.

But we know they must be true so we can make use of them if we need to.

This is called "strong" induction. It is equivalent to weak induction. The only difference is we might need to make use of earlier values than just the $x-1$ case.

This can be particularly useful with recursive definitions.

Say you know that $a_1 = something$ and $a_n = $ something to do with $a_{n-1}$ if $n$ is odd and something to do with $a_{\frac n2}$ and $a_{n-1}$ if $n$ is even. And you want to prove something about $a_n$. Well, it is not just enough to assume that the proposition is true of $a_{n-1}$. You also have to assume it is true of $a_{\frac n2}$. Can you assume that? Of course you can. To get to $a_{n-1}$ you had to have "passed through" $a_{\frac n2}$ "along the way". So why not use it if you have it?

$\endgroup$

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.