Principiul inducției matematice
Am văzut în lecțiile anterioare că predicatele sunt propoziții care depind de una sau mai multe variabile.
Să considerăm că 𝑃 𝑛 , 𝑛 ∈ 𝑁 est un astfel de predicat care depinde de variabila 𝑛 ∈ 𝑁, 𝑛 ≥ 𝑚 ( m fiind fixat în enunț ).
𝑛 𝑛+1
De exemplu : 𝑃 𝑛 : 1 + 2 + 3 + ⋯ + 𝑛 = , ∀𝑛 ∈ 𝑁 ∗
n numere
2
Dacă
a) propoziția 𝑃 𝑚 este adevărată ( verificare prin calcul efectiv )
Și
b) demonstrăm adevărul ( verificare prin calcul efectiv )
pentru implicația 𝑃(𝑘) ⇒ 𝑃(𝑘 + 1) pentru orice număr natural 𝑘, 𝑘 ≥ 𝑚.
atunci
propoziția 𝑃 𝑛 este adevărată pentru orice 𝑛 ∈ 𝑁, 𝑛 ≥ 𝑚
𝑛 𝑛+1
Să demonstrăm exemplul de mai sus 𝑃 𝑛 :1 + 2 + 3 + ⋯+ 𝑛 = , ∀𝑛 ∈ 𝑁 ∗
n numere
2
Cum 𝑛 ∈ 𝑁 ∗ înseamnă că 𝑛 ∈ 𝑁, 𝑛 ≥ 1 adică 𝑚 = 1
a) Verificăm dacă propoziția 𝑃 1 este adevărată ( verificare prin calcul efectiv )
1 1+1
𝑃 1 :1 = ⇔ 1 = 1 evident adevărat
2
1 număr
b) demonstrăm adevărul ( verificare prin calcul efectiv )
pentru implicația 𝑃(𝑘) ⇒ 𝑃(𝑘 + 1) pentru orice număr natural 𝑘, 𝑘 ≥ 𝑚.
𝑘 𝑘+1
Pentru ușurință, scriem separat 𝑃 𝑘 : 1 + 2 + 3 + ⋯ + 𝑘 = propoziție pe care o considerăm logic adevărată
2
k numere
𝑘 + 1 (𝑘 + 2)
Și trebuie să verificăm dacă 𝑃 𝑘 + 1 : 1 + 2 + 3 + ⋯ + 𝑘 + (𝑘 + 1) = este propoziție adevărată.
2
k+1 numere
Pentru aceasta calculăm efectiv membrul stâng al lui 𝑃 𝑘 + 1 și avem
𝑘 𝑘+1 𝑘 𝑘 + 1 (𝑘 + 2)
1 + 2 + 3 + ⋯+ 𝑘 + 𝑘 + 1 = + 𝑘+1 = 𝑘+1 +1 = așadar 𝑃(𝑘 + 1) este adevărată
𝑓𝑜𝑙𝑜𝑠𝑖𝑚 𝑃(𝑘)
2 2 2
atunci propoziția 𝑃 𝑛 este adevărată pentru orice 𝑛 ∈ 𝑁, 𝑛 ≥ 1