Does this constitute a proof? - Infinite reduction of criteria

66 Views Asked by At

Lets say I have a conjecture that I need to prove true for all integers. And I find a way to reduce the problem to only numbers of the form:

$N ≡ 1\pmod{2}$

But in doing so also then find a way to reduce the problem to only numbers of the form

$N ≡ 1\pmod{4}$

and again to $N ≡ 1\pmod{8}$

and further to $N ≡ 1\pmod{16}$

then suppose I found an inductive way to show that if I have reduced it to $N ≡ 1\pmod{2^n}$, then I can further reduce the problem to $N ≡ 1\pmod{2^{n+1}}$

Taking this to its limit, I would then have to only prove the problem true for $N ≡ 1\pmod{ ∞}$ - Ignoring the casual use of infinity for lack of better notation.

Would it constitute a proof to show that my problem is true for $N=1$ and therefore all numbers?

I feel like by the nature of this structure being setup that the underlying conjecture must be true.

2

There are 2 best solutions below

3
On BEST ANSWER

Consider the statement $P(N)$ which says "$N=1$, or $N$ is both even and odd". The statement "$P(1)$" is true. The statement "if $P(N)$ is true for all $N \equiv 1$ mod $4$ then $P(N)$ is true for all $N \equiv 1$ mod $2$" is also true, which reduces the mod 2 statement to the mod 4 statement. The statement "if $P(N)$ is true for all $N \equiv 1$ mod 8 then $P(N)$ is true for all $N \equiv 1$ mod $4$" is also true, which reduces the mod 4 statement to the mod 8 statement. And so on, so the mod $2^k$ statement may be reduced to the mod $2^{k+1}$ statement for all $k$. But $P(N)$ is true only for $N=1$.

1
On

Simply verifying $N=1$ would not be sufficient. You'd need to prove it for some $n$, since you can't induct backwards from $\infty$.