1

This is probably a stupid question.

Let us say I were to prove something by induction. Is it true, that the basecase must be the lowest possible number? If I wanted to prove that the formula holds for 1, 2, 3, ... , 999 for example, the basecase cannot be 5 right? Logically, if it holds for 5, it does not necessarily hold for 4, 3, 2 and 1, correct?

Arcthor
  • 91

2 Answers2

3

With induction we usually prove something for all integers bigger than or equal to the base case value. If we show that a statement holds for $n=5$, and show that if it holds for $n$ then it holds for $n+1$, we have shown that the statement holds for all integers greater than or equal to $5$. However, nothing stops you from also using induction in the other direction: That is, also prove that if it holds for $n$ then it holds for $n-1$. Nów if we can show that the statement holds for an arbitrary base case, we have automatically proven it for any integer! (This form of induction isn't very common though).

Uncountable
  • 3,520
  • 1
    A more common sort of "induction" on the integers proves $n\to n+1$ and $n\to-n$. For example, proving that $f(x+y)=f(x)+f(y)$ is linear on the integers. – Mario Carneiro Feb 17 '15 at 16:10
  • Okay, so if we prove that s(p) => s(p+1), that is NOT the same as saying s(p+1) => s(p)? – Arcthor Feb 17 '15 at 16:50
  • Yes, this is a basic property of the implication. If I win the lottery I am happy, but in order to be happy I don't have to necessarily win the lottery. $A\implies B$ is not the same as $B\implies A$. – Uncountable Feb 17 '15 at 16:55
0

The base case can be 5, as long as you prove the cases 1,2,3 and 4 in some other way.

MarkG
  • 532
  • Okay, so if we prove that s(p) => s(p+1), that is NOT the same as saying s(p+1) => s(p)? – Arcthor Feb 17 '15 at 16:56
  • It is NOT the same thing. If you prove $s(p) \implies s(p+1)$ for all $p$ AND you prove $s(5)$, then you get that $s(6)$ holds (by the implication), $s(7)$ holds (by the implication applied to $s(6)$), ... But you cannot use $s(p) \implies s(p+1)$ to prove $s(4)$ (unless you prove $s(3)$). – MarkG Feb 17 '15 at 17:01