Induction mathematique

Mathematical induction, est une technique pour prouver des résultats ou établir des déclarations pour des nombres naturels. Cette partie illustre la méthode à travers une variété d'exemples.

Définition

Mathematical Induction est une technique mathématique qui est utilisée pour prouver qu'un énoncé, une formule ou un théorème est vrai pour chaque nombre naturel.

La technique implique deux étapes pour prouver une déclaration, comme indiqué ci-dessous -

Step 1(Base step) - Cela prouve qu'une déclaration est vraie pour la valeur initiale.

Step 2(Inductive step)- Cela prouve que si l'énoncé est vrai pour la n ^ième itération (ou le nombre n ), alors il l'est également pour la (n + 1) ^ième itération (ou le nombre n + 1 ).

Comment faire

Step 1- Considérez une valeur initiale pour laquelle l'énoncé est vrai. Il faut montrer que l'énoncé est vrai pour n = valeur initiale.

Step 2- Supposons que l'énoncé est vrai pour toute valeur de n = k . Ensuite, prouvez que l'énoncé est vrai pour n = k + 1 . Nous divisons en fait n = k + 1 en deux parties, une partie est n = k (ce qui est déjà prouvé) et essayons de prouver l'autre partie.

Problème 1

$ 3 ^ n-1 $ est un multiple de 2 pour n = 1, 2, ...

Solution

Step 1 - Pour $ n = 1, 3 ^ 1-1 = 3-1 = 2 $ qui est un multiple de 2

Step 2 - Supposons que $ 3 ^ n-1 $ est vrai pour $ n = k $, donc, $ 3 ^ k -1 $ est vrai (c'est une hypothèse)

Nous devons prouver que $ 3 ^ {k + 1} -1 $ est aussi un multiple de 2

$ 3 ^ {k + 1} - 1 = 3 \ fois 3 ^ k - 1 = (2 \ fois 3 ^ k) + (3 ^ k - 1) $

La première partie $ (2 \ times 3k) $ est certaine d'être un multiple de 2 et la deuxième partie $ (3k -1) $ est également vraie comme notre hypothèse précédente.

Par conséquent, $ 3 ^ {k + 1} - 1 $ est un multiple de 2.

Ainsi, il est prouvé que $ 3 ^ n - 1 $ est un multiple de 2.

Problème 2

$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ pour $ n = 1, 2, \ points $

Solution

Step 1 - Pour $ n = 1, 1 = 1 ^ 2 $, donc l'étape 1 est satisfaite.

Step 2 - Supposons que l'énoncé soit vrai pour $ n = k $.

Par conséquent, $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $ est vrai (c'est une hypothèse)

Nous devons prouver que $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $ vaut aussi

$ 1 + 3 + 5 + \ points + (2 (k + 1) - 1) $

$ = 1 + 3 + 5 + \ points + (2k + 2 - 1) $

$ = 1 + 3 + 5 + \ points + (2k + 1) $

$ = 1 + 3 + 5 + \ points + (2k - 1) + (2k + 1) $

$ = k ^ 2 + (2k + 1) $

$ = (k + 1) ^ 2 $

Donc, $ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) = (k + 1) ^ 2 $ hold, ce qui satisfait l'étape 2.

Par conséquent, $ 1 + 3 + 5 + \ dots + (2n - 1) = n ^ 2 $ est prouvé.

Problème 3

Prouvez que $ (ab) ^ n = a ^ nb ^ n $ est vrai pour tout nombre naturel $ n $

Solution

Step 1 - Pour $ n = 1, (ab) ^ 1 = a ^ 1b ^ 1 = ab $, par conséquent, l'étape 1 est satisfaite.

Step 2 - Supposons que l'énoncé soit vrai pour $ n = k $, donc $ (ab) ^ k = a ^ kb ^ k $ est vrai (c'est une hypothèse).

Nous devons prouver que $ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ est également valable

Étant donné, $ (ab) ^ k = a ^ kb ^ k $

Ou, $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [Multiplier les deux côtés par 'ab']

Ou, $ (ab) ^ {k + 1} = (aa ^ k) (bb ^ k) $

Ou, $ (ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1}) $

Par conséquent, l'étape 2 est prouvée.

Donc, $ (ab) ^ n = a ^ nb ^ n $ est vrai pour tout nombre naturel n.

Induction forte

L'induction forte est une autre forme d'induction mathématique. Grâce à cette technique d'induction, nous pouvons prouver qu'une fonction propositionnelle, $ P (n) $ est vraie pour tous les entiers positifs, $ n $, en utilisant les étapes suivantes -

• Step 1(Base step) - Cela prouve que la proposition initiale $ P (1) $ est vraie.

• Step 2(Inductive step) - Cela prouve que l'instruction conditionnelle $ [P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1) $ est vraie pour les entiers positifs $ k $.