Complete induction

Encyclopedia : C : CO : COM : Complete induction

---

In mathematics, complete induction, also known as strong induction, is a variant on the principle of mathematical induction. The induction hypothesis, instead of being simply

[P(n-1)\,\! ,]

is

[\forall i \in \left\ P(i).\,]

This is clearly a stronger hypothesis, hence the name strong induction. It is a fact that anything provable with mathematical induction is provable with strong induction.

On the other hand it requires only the introduction of a new proposition Q(n) which is the logical conjunction of the P(m) for 0 ≤ m ≤ n to write a strong induction argument as a conventional induction. This is sometimes done implicitly, as in minimal counterexample arguments by contradiction.

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?