0

what is the fault in this reasoning by strong induction

For all $ A $ and $ B $ of $ M_p (K) $ and all integer $n$ we have: $ A ^ n B = B $

The proof :

Denote $\forall n\in \mathbb N,\quad P (n) $ : $ A ^ n B = B $

  • The property is true at rank $ n = 0 $ because $ A ^ 0 B = I_n B = B $

  • Let $ n $ be a natural integer, suppose $ P (n) $ true up to rank $ n $. $ A ^ {n + 1} B = A A ^ n B = AB $ (hypothesis at rank $ n $) and $ A B = B $ (assumption at rank $ 1 $) we thus obtain $ A ^ {n + 1} B = B $

and $ P (n + 1) $ is true

Pascal
  • 3,771

1 Answers1

1

In the inductive step you're only allowed to use previous steps. $P(1)$ is not a previous step for $P(1).$

The inductive step requires that $P(1)$ is already true, which is valid for $P(n)$ for all $n \geq2,$ but since you only have $P(0)$ as a base case you needed an inductive step that is valid for all $n \geq 1.$

David K
  • 98,388
  • The link I gave therefore contains an error ? – Pascal Jul 06 '20 at 22:24
  • The link has one particularly bad defect, in my opinion, because it does not say what values of $n$ they mean. It should say something like "arbitrary $n$ where $n > 0.$" Moreover, even that wording requires a certain understanding of what they mean by "arbitrary" $n.$ What it ought to mean is, you have to prove an inductive step that is true no matter which $n$ it is applied to as long as $n$ is an integer and $n>0.$ It does not mean you get to pick your own choice of $n$ that can be as large as you want and only do a proof for that value of $n.$ – David K Jul 06 '20 at 22:31
  • The previous page, for weak induction, is a bit better, because in that case you're asked to prove $P(n+1)$ for arbitrary $n$, and in this case the arbitrary $n$ is any $n\in \mathbb N$, not just $n>0.$ – David K Jul 06 '20 at 22:34
  • They actually do say what they mean by "arbitrary": if you click on the word "arbitrary" it takes you here: https://courses.cs.cornell.edu/cs2800/wiki/index.php/Choose_an_arbitrary_value – David K Jul 06 '20 at 22:35
  • Why negative votes, we are not allowed to ask a question even stupid? – Pascal Jul 06 '20 at 22:36
  • You're right, I don't agree with the negative vote on the question. Your argument is actually a classic fallacy used in multiple "fake proofs" that people have made up to puzzle others, which makes it all the more legitimate as a question. – David K Jul 06 '20 at 22:54
  • Thank's David for your explanation and support – Pascal Jul 06 '20 at 23:43