Induzione matematica

Mathematical induction, è una tecnica per provare risultati o stabilire affermazioni per numeri naturali. Questa parte illustra il metodo attraverso una varietà di esempi.

Definizione

Mathematical Induction è una tecnica matematica che viene utilizzata per dimostrare che un'affermazione, una formula o un teorema è vero per ogni numero naturale.

La tecnica prevede due passaggi per dimostrare una dichiarazione, come indicato di seguito:

Step 1(Base step) - Dimostra che un'affermazione è vera per il valore iniziale.

Step 2(Inductive step)- Dimostra che se l'affermazione è vera per l' ^ennesima iterazione (o numero n ), allora è vero anche per (n + 1) ^esima iterazione (o numero n + 1 ).

Come farlo

Step 1- Considera un valore iniziale per il quale l'affermazione è vera. È da dimostrare che l'affermazione è vera per n = valore iniziale.

Step 2- Supponiamo che l'affermazione sia vera per qualsiasi valore di n = k . Quindi prova che l'affermazione è vera per n = k + 1 . In realtà rompiamo n = k + 1 in due parti, una parte è n = k (che è già stato dimostrato) e proviamo a dimostrare l'altra parte.

Problema 1

$ 3 ^ n-1 $ è un multiplo di 2 per n = 1, 2, ...

Solution

Step 1 - Per $ n = 1, 3 ^ 1-1 = 3-1 = 2 $ che è un multiplo di 2

Step 2 - Supponiamo che $ 3 ^ n-1 $ sia vero per $ n = k $, quindi $ 3 ^ k -1 $ sia vero (è un presupposto)

Dobbiamo dimostrare che $ 3 ^ {k + 1} -1 $ è anche un multiplo di 2

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

La prima parte $ (2 \ times 3k) $ è sicuramente un multiplo di 2 e anche la seconda parte $ (3k -1) $ è vera come la nostra ipotesi precedente.

Quindi, $ 3 ^ {k + 1} - 1 $ è un multiplo di 2.

Quindi, è dimostrato che $ 3 ^ n - 1 $ è un multiplo di 2.

Problema 2

$ 1 + 3 + 5 + ... + (2n-1) = n ^ 2 $ per $ n = 1, 2, \ punti $

Solution

Step 1 - Per $ n = 1, 1 = 1 ^ 2 $, quindi, il passaggio 1 è soddisfatto.

Step 2 - Supponiamo che l'affermazione sia vera per $ n = k $.

Quindi, $ 1 + 3 + 5 + \ dots + (2k-1) = k ^ 2 $ è vero (è un presupposto)

Dobbiamo dimostrare che vale anche $ 1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2 $

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

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

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

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

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

$ = (k + 1) ^ 2 $

Quindi, $ 1 + 3 + 5 + \ dots + (2 (k + 1) - 1) = (k + 1) ^ 2 $ mantieni il che soddisfa il passaggio 2.

Quindi, $ 1 + 3 + 5 + \ dots + (2n - 1) = n ^ 2 $ è dimostrato.

Problema 3

Dimostrare che $ (ab) ^ n = a ^ nb ^ n $ è vero per ogni numero naturale $ n $

Solution

Step 1 - Per $ n = 1, (ab) ^ 1 = a ^ 1b ^ 1 = ab $, quindi, il passaggio 1 è soddisfatto.

Step 2 - Supponiamo che l'affermazione sia vera per $ n = k $, quindi $ (ab) ^ k = a ^ kb ^ k $ è vera (è un'assunzione).

Dobbiamo dimostrare che $ (ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1} $ vale anche

Dato, $ (ab) ^ k = a ^ kb ^ k $

Oppure $ (ab) ^ k (ab) = (a ^ kb ^ k) (ab) $ [Moltiplicando entrambi i lati per 'ab']

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

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

Quindi, il passaggio 2 è dimostrato.

Quindi, $ (ab) ^ n = a ^ nb ^ n $ è vero per ogni numero naturale n.

Forte induzione

L'induzione forte è un'altra forma di induzione matematica. Attraverso questa tecnica di induzione, possiamo dimostrare che una funzione proposizionale, $ P (n) $ è vera per tutti i numeri interi positivi, $ n $, utilizzando i seguenti passaggi:

• Step 1(Base step) - Dimostra che la proposizione iniziale $ P (1) $ è vera.

• Step 2(Inductive step) - Dimostra che l'affermazione condizionale $ [P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1) $ è vera per interi positivi $ k $.