0
$\begingroup$

Mathematical induction Follows Thus:

$1.$ The basis (base case): prove that the statement holds for the first natural number $n$. Usually, $n = 0$ or $n = 1$.

$2.$ The inductive step: prove that, if the statement holds for some natural number $n$, then the statement holds for $n + 1$.

For example, when $F_{n}$ is the $n$th Fibonacci Number, it is known that $${ { F }_{ 1 } }^{ 2 }+{ { F }_{ 2 } }^{ 2 }+\dots+{ { F }_{ n } }^{ 2 }=F_nF_{n+1}$$

$1$. When $n=1$, ${ { F }_{ 1 } }^{ 2 }=1=F_1F_{2}$

$2$. Assume that the statement is true for $n-1$. Then ${ { F }_{ 1 } }^{ 2 }+{ { F }_{ 2 } }^{ 2 }+\dots+{ { F }_{ n } }^{ 2 }=F_nF_{n-1}+{ { F }_{ n } }^{ 2 }=F_nF_{n+1}$.

However, what if we show that if the statement is not true for $n+1$, then it is not true for $n$? For example, assume ${ { F }_{ 1 } }^{ 2 }+{ { F }_{ 2 } }^{ 2 }+\dots+{ { F }_{ n } }^{ 2 }\neq F_nF_{n+1}$.

Substracting ${ { F }_{ n } }^{ 2 }$ on both sides gives us that ${ { F }_{ 1 } }^{ 2 }+{ { F }_{ 2 } }^{ 2 }+\dots+{ { F }_{ n-1 } }^{ 2 }\neq F_nF_{n-1}$.

Keep substracting ${ { F }_{ i } }^{ 2 }$, and this gives us that ${ { F }_{ 1 } }^{ 2 } \neq F_1F_{2}$. A contradiction.

It appeared to me that this was not induction, rather a proof by contradiction. Is this or is this not mathematical induction? Any insight would be appreciated.

$\endgroup$
0
$\begingroup$

It is an inductive proof. When you have an inductive proof you require two "subproofs" a proof for the base step and a proof for the inductive step. In this case your proof for the inductive step is a proof by contradiction.

$\endgroup$
  • $\begingroup$ How so? There does not appear to be two subproofs, in my opinion. Is the fact that $F_{1}^2 \neq F_{1}F_{2}$ the base step then? or is it the inductive step? $\endgroup$ – Chad Shin Feb 3 '16 at 4:07

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.