Sesiunea Naţională de Comunicări Ştiinţifice pentru profesorii de matematică

8-9 noiembrie 2013

INDUCŢIA MATEMATICĂ… ALTFEL

1

PROF. ROXANA GOGALICEUL TEORETIC BILINGV “ITA WEGMAN”, BUCUREŞTI

2

MOTTO:Miron Nicolescu, matematician român

“Principiul inducţiei complete constituie unul dintre cele mai puternice raţionamente de demonstraţie în matematică”.

3

O SCURTĂ INTRODUCERE…

Raţionamentul inductiv apare pentru prima dată la Blaise Pascal, care îl utilizează în demonstrarea formulei combinărilor şi pe care-l descrie astfel: “Deşi această propoziţie conţine infinit de multe cazuri, voi da o demonstraţie foarte scurtă care presupune două Leme. Prima Lemă afirmă că pentru prima linie propoziţia este adevarată. Lema a doua afirmă că dacă propoziţia se dovedeşte adevarată pentru o linie oarecare atunci propoziţia este valabilă şi pentru linia următoare”.

Sigur putem spune că este o variantă apropiată de studiul inducţiei de astăzi.    

4

DE-A LUNGUL ISTORIEI…

Al-Karajimatematician

Prima demonstraţie prin inducţie matematică apare pentru progresii aritmetice în cartea “al-Fakhri” scrisă de al Karaji în jurul anului 1000 IH. Proprietăţi ale triunghiului lui Pascal sunt de asemenea demonstrate aici.

Nici unul dintre matematicienii lumii antice nu au considerat principiul inducţiei matematice de sine stătător.

Prima prezentare explicită apare în lucrarea Arithmeticorum libri duo (1575) a lui Francesco Maurolico care demonstrează că suma primelor n numere impare este n 2 . Formularea principiului inducţiei matematice apare în lucrarea lui Pascal Traité du triangle arithmétique (1665).

Apoi prin Fermat, Jacob Bernoulli principiul inducţiei este extins, folosit în demonstraţii. Secolul al XIX-lea aduce studiul sistematic al acestui principiu în logica matematică prin matematicienii George Boole, Charles Sanders Peirce, Giuseppe Peano şi Richard Dedekind.

Astăzi metoda inducţiei matematice este aplicată în cele mai variate probleme de matematică, devenind un instrument uzual si

eficace.

RAŢIONAMENTUL INDUCTIV

Modalitatea de a obţine cunoştinţe ştiinţifice noi, din cele deja cunoscute o constituie raţionamentul inducţiei matematice.

Raţionamentul deductiv, adică raţionamentul demonstrativ al inducţiei face trecerea de la general la particular.

Rezultatele obţinute sunt certe însă au un caracter particular.

Raţionamentul inductiv (unul din raţionamentele plauzibile) este foarte important pentru faptul că ne conduce pe baza unor situaţii particulare cunoscute la concluzii generale, care ar putea însă să nu fie adevărate.

PRINCIPIUL INDUCŢIEI MATEMATICE

Principiul inducţiei matematice constă în a demonstra că o propoziţie P(n) este adevărată pentru orice număr natural n dacă se verifică condiţiile:

1. propoziţia este adevărată pentru n=n0.

2. presupunând că propoziţia este adevărată pentru un n=k oarecare se demonstrează că propoziţia este adevărată pentru n=k+1. Acesta fiind efectiv pasul de inducţie şi de altfel cel mai important. Pe scurt: scriem că P(k) =>P(k+1).

Astfel putem face afirmaţia că propoziţia este adevărată pentru orice număr natural n aplicând raţionamentul inducţiei matematice.

“EFECTUL DE DOMINO”

Inducţia matematică poate fi asemănată cu “efectul de domino”.

Să considerăm prin analogie că:P(n) ar fi: “Al n-lea domino se dărâmă”.Dacă (a) “P(1) este adevărat”; (Primul domino se dărâmă.)

(b) “P(k) este adevărat” implică “P(k+1) adevărat” (Dacă dominul k se dărâmă implică dominoul k+1 se dărâmă)Deci P(n) este adevărată pentru orice n.Toate dominourile se dărâmă.

INDUCŢIA IN GIMNAZIU

Pentru elevii din clasele V-VI un astfel de raţionament deductiv, folosind pasul de inducţie matematică în general este greu de înţeles, dar putem folosi pentru demonstraţii situaţii particulare de trecere de la pasul n la pasul n+1 pentru n natural mic, adică pentru valori concrete ale lui n.

Pe de o parte putem obţine demonstraţii perfect corecte pentru valori concrete ale lui n, iar pe de altă parte elevul poate extrapola rezultatul şi demonstraţia în cazul general.

PAŞI SPRE INDUCŢIE

Aceste raţionamente sunt greu de explicat în situaţii algebrice “identităţi, inegalităţi”,dar în anumite probleme de combinatorică sau aritmetică pot fi înţelese în cazuri numerice.

Inducţia matematică poate fi “simţită” ca mod de demonstraţie, de copii, în special în formule de numărare şi probleme ce nu necesită cunoştinţe algebrice.

Experienţa arată că pasul de la 2 la 3, de la 3 la 4, … poate să-i convingă pe copii că aceeaşi metodă funcţionează pentru orice trecere şi că rezultatul devine astfel valabil.

EXEMPLE:

Numărul de permutări al unei mulţimi cu 2,3,4,5,…elemente

Numărul de aranjamente de câte 2,3,4,5 al unei mulţimi cu 6, 7 elemente.

Numărul de combinări de câte 2,3,4,5 al unei mulţimi cu 6, 7 elemente.

SUMA LUI GAUSS

Carl Friedrich Gauss(39 Aprilie 1777-23 Februarie 1855),

este considerat cel mai mare matematician, geniu, după Arhimede.Cartea care a intemeiat teoria modernă a numerelor este

” Disquitiones Arithmeticae” publicată în anul 1801. Suma Gauss este atribuită lui Gauss, copil fiind, acest rezultat matematic fiind cunoscut încă din antichitate în China prin numerele triunghiulare n(n+1):2. Acest număr este egal cu un număr de puncte format din triunghiuri echilaterale alegând pe laturile sale un număr de puncte care formează alte triunghiuri echilaterale.

P(n): Conform raţionamentului suntem siguri că proprietatea poate fi adevarată dacă verificăm

primul pas al inducţiei pentru n=1, anume:

Dacă P(1) este adevărată: 1 = Astfel, 1=1. Trecem la pasul de inducţie P(k) P(k+1). Vom scrie pentru început cine este P(k), înlocuind n=k în propoziţia dată P(n) obţinem:

P(k): 1+2+3+...+k = , pentru orice k. Demonstrăm în continuare că pentru n=k+1 propoziţia este adevărată: P(k+1): 1+2+3+...+k+(k+1)= Conform presupunerii că P(k) este adevărată vom studia membrul stâng din P(k+1) :

1+2+3+...+k+(k+1)=

Astfel am demonstrat că P(k+1) este adevărată. Conform metodei inducţiei matematice P(n) este adevărată pentru orice n.

*( 1)1 2 3 ... ,

2

n nn n

1 (1 1)

2

(1)

2

kk

( 1)( 2)

2

k k

( 1) ( 1)( 2)1

2 2

k k k kk

ALTE EXEMPLE:

APLICAŢII ALE INDUCŢIEI MATEMATICE ÎN DIVIZIBILITATE

• Să se arate că numărul 2n +1 nu se divide cu 7 pentru orice n număr natural.• Determinaţi toate numerele naturale n care indeplinesc condiţia că • 2n -1 se divide cu 7.• Arătaţi ca 7n-1 este multiplu de 6 pentru orice n numar natural nenul.• Arătaţi ca 72n+1+1 este multiplu de 8 pentru orice n număr natural.• Arătaţi că 4n+15n-1 este multiplu de 9 pentru orice n numar natural nenul.

INEGALITATI

• Arătaţi că 3n≥n3 pentru orice număr natural n≥3. • Arătaţi că 2n≥n2 pentru orice număr natural n≥4. • Arătaţi că 2n≥n4 pentru orice număr natural n≥16.  

Inegalităţi şi grafice

NU ORICE INEGALITATE POATE FI DEMONSTRATĂ PRIN INDUCŢIE

MATEMATICĂ DATORITĂ SUFICIENŢEI

CONTRAEXEMPLU:2 2 2

2 2 2

2 2 2 2

2 2 2 2

2 2 2 2 2

1 1 1Fie P(n): ... 2

1 21 1 1

Avem P(k): ... 2adevarata si studiem daca1 2

1 1 1 1( 1) : ... 2esteadevarata.

1 2 ( 1)

1 1 1 1Adunand P(k): ... 2cu

1 2 ( 1)

1 1 1 1 1... 2 2

1 2 ( 1) ( 1)

cee

n

k

P kk k

k k

k k k

a cecontrazice P(k+1).

Observăm că există situaţii în care ipoteza de inducţie nu poate fi construită în aşa fel incât să poată fi folosită în demontraţii pentru anumite inegalităţi.

EXEMPLE NETRIVIALE

1. Problemă dată la concursul tip OIM – Călăraşi 2008

Se dau numerele raţionale cu proprietatea că suma lor şi produsul a oricăror două este număr întreg. Arătaţi că toate numerele sunt întregi.Comentariu:Pentru n=2 este un exerciţiu de divizibilitate abordabil pentru copiii din clasele V-VI. Trecerea de la două numere la trei numere exemplifică cele afirmate în preambul.

1 2 3, , ... na a a a

CAZURI PARTICULARE

Putem considera două numere Acestea verifică ipoteza pentru două numere. Din

cazul respectiv rezultă că a şi b sunt întregi. Plecând analog cu numerele rezultă că acestea sunt întregi. Este un exerciţiu de rutină pentru copii să deducă de aici că toate cele trei numere sunt întregi.

1 2 3,a a b a a

1 2 3,a a a

INDUCŢIA TARE

Inducţia tare, reprezintă o noţiune adesea folosită pentru a desemna un raţionament echivalent inducţiei standard, în care ipoteza de inducţie pentru o singură variabilă este inlocuită cu cea în care se presupun adevarate mai multe astfel de propoziţii.

Astfel gândim că P(n0) este adevarată, verificând că această propoziţie este adevărată pentru n=n0. Demonstrăm apoi că dacă propoziţia este adevarată pentru orice număr natural m mai mic sau egal cu n (n0≤m≤n). Atunci propoziţia este adevărata şi pentru n+1. Rezultă că propoziţia este adevarata pentru orice n≥n0.

EXEMPLUL 1.

Fie relaţia an+1= 3an – 2an-1 ; a1= 3; a2=5. Demonstraţi că:

an= 1+2n, pentru orice n≥1.

SOLUŢIE:

Verificăm relaţiile pentru n=1: a1=1+2=3. a2= 1+22=5.

Presupunem că relaţia este adevărată pentru orice număr k≤n şi demonstrăm că pentru k=n+1 este îndeplinită relaţia an+1= 1+2n+1;

Într-adevăr avem că an+1= 3an – 2an-1 = 3(1+2n)-2(1+2n-1)=

= 3+3·2n-2-2·2n-1=1+2n-1(3·2-2)=1+2n-1·4=1+2n+1. Q.E.D.

EXEMPLUL 2.

Pentru orice număr natural n avem:SOLUŢIE:

Verificăm relaţiile pentru n=1:

P(1):Fie

Astfel formez ecuaţia de gradul al doilea cu rădăcinile x1 şi x2

x2 - 4x-1 = 0. Înmulţind aceasta cu x1k-1 si cu x2

k-1 obţinem

următoarele relaţii: x1k+1 - 4x1

k - 1 = 0 ; x2k+1 - 4x2

k - 1 = 0 ;

Arătăm că P(k) P(k+1). Adică dacă P(k) este adevărată atunci şi P(k+1) este adevărată.

Fie x1k+1 + x2

k+1 = 4·( x1k + x2

k)+2 dar cum am presupus că

x1k+1 + x2

k+1 Z rezultă că şi x1k+1 + x2

k+1 Z.

(2 5) (2 5)n n

1 2 1 2 1 22 5, 2 5 4, 1 .x x x x x x

INDUCŢIA ÎN GEOMETRIE:PROBLEMĂ CLASICĂ (Probleme neelementare

tratate elementar M.Yaglom, I.Yaglom)

Planul este împărţit într- un număr de regiuni prin n drepte. Să se arate că regiunile pot fi colorate cu roşu şi albastru astfel încât oricare două regiuni învecinate având un segment sau o semidreaptă comună sunt colorate diferit.

Rationamentul de trecere la o dreapta suplimentară în care de o parte a ei se schimbă culorile poate fi uşor înţeles de către copii în inducţia de la 2 la 3, de la 4 la 5, chiar şi în cazul general.

Trecerea de la 3 la 4 drepte

Numărul maxim de regiuni în care planul poate fi împărţit prin n drepte este egal cu:

Pentru a demonstra această afirmaţie facem apel la metoda inducţiei matematice, considerând ca propoziţie:

P(n): „ n drepte împart planul în cel puţin regiuni”.

Verificarea primei propoziţii constă în

P(1): pentru n=1 avem că o dreaptă împarte planul în regiuni.

Presupunem că proprietatea este adevărată pentru n=k, şi astfel avem:

P(k): „ k drepte împart planul în regiuni”.

Adăugăm o dreaptă în plan, care să nu fie paralelă cu celelalte, suficient de departe astfel încât să intersecteze toate cele k drepte. Astfel avem încă k+1 regiuni.

Rezultă aşadar că împărţit în regiuni.

( 1)1

2

n n

( 1)1

2

n n

1 21 2

2

( 1)1

2

k k

( 1) ( 1)( 2)1 ( 1) 1

2 2

k k k kk

Să se demonstreze că pentru orice număr natural n, n≥6 un pătrat poate fi împărţit în n pătrate.

Soluţie: Se verifică ipoteza de inducţie pentru n=6,7,8, adică verificăm dacă P(6), P(7), P(8) sunt adevărate.

Demonstrăm pasul de inducţie, adică implicaţia:

P(n) P(n+3).

Presupunând făcută împărţirea în n pătrate, unul dintre ele se împarte în patru pătrate egale şi se obţin în acest fel n+3 pătrate.

Astfel implicaţia:P(n) P(n+3) este adevărată şi conform raţionamentului inducţiei matematice P(n) este adevărată pentru orice număr natural n≥6. 

1.Trebuie imprimată convingerea că metoda inducţiei matematice complete este o metodă puternică de demonstraţie aplicabilă în toate domeniile matematicii.

2. O serie de probleme considerate cu un grad sporit de dificultate, probleme de tip OIM, apreciate ca non-standard sunt rezolvabile destul de uşor prin metoda inducţiei matematice.

3. Este necesar că propoziţia matematică P(n) să fie clar formulată, deoarece o serie de probleme fac posibilă alegerea mai multor ipoteze de inducţie optând pentru cele în care demonstraţia este mai simplă .

4. Există uneori tendinţa ca prima etapă de verificare să fie neglijată, fiind foarte simplă. Trebuie ca elevii să fie deprinşi a acorda aceeaşi importanţă ambelor etape, întrucât P(n0) se pote dovedi falsă. Uneori etapa de verificare poate fi partea dificilă a raţionamentului, sau cea importantă.

CONCLUZII

5. Inducţia există şi în alte ştiinţe, nu întotdeauna rezultatele fiind adevărate. Astfel trebuie dat importantă egală ambelor etape distincte: etapei de verificare şi etapei de demonstraţie (pasul de inducţie).

6. Este necesar ca elevilor sa le fie prezentate probleme matematice demonstrate prin raţionamentul inducţiei matematice din cât mai multe ramuri ale matematicii şi cât mai variate pentru a sesiza diversitatea aplicării raţionamentului şi necesitatea reţinerii de către elevi şi a altor variante de demonstrare ale metodei.

7. Se subliniază elevilor faptul că raţionamentul inducţiei matematice este demostrabil în situaţia în care există o situaţie logică care permite trecerea de la un pas la următorul, de la n la n+1.

CONCLUZII

BIBLIOGRAFIE

Inducţia matematică-Laurenţiu PANAITOPOL

Cercurile de matematică din MOSCOVA

VĂ

MULŢUMESC

PENTRU

ATENŢIE!