Прилагане на метода на математическа индукция

3) етап на индуциране: докаже, че изложението е вярно за п = к + 1, т.е. ..

1 + 3 + 5 +. + (2k - 1) + (2k + 1) = (к + 1) 2. Според предположението, сумата от първите к термини в лявата ръка е равна на к 2. И така, какво е необходимо да се докаже, може да се запише като:

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

но това е очевидно.

Пример 15. докаже, че за всяко естествено число п 3 п + 5N неделими от 6.

Доказателство. Индукция база включва: когато п = 1, числото п 3 + 5N = 6, разделена 6. Да предположим, че за някои номера к 3 К + 5k неделими от 6. Използване това, се опита да се докаже, че ако и (к + 1) + 3 5 (к + 1) се дели на 6. превръщане Draw:

(К + 1) 3 + 5 (к + 1) = к 3 + 3k 2 + 3k + 1 + 5k + 5 = = (к 3 + 5k) + (3k 2 + 3к) + 6 = (к 3 + 5k ) + 3k (к + 1) + 6.

Първият термин в тази сума се разделя на 6, чрез допускане, вторият също се дели на 6, поради номера к, к + 1 един непременно дори. Следователно, цялата сума се дели на 6, както се изисква.

Като друг пример, ние доказваме теоремата за броя на подгрупи на крайно множество.

Теорема 4. набор се състои от п елементи, п е две различни подгрупи.

Доказателство. Ние използваме индукция върху Броят п. Ако набор А = състои от един елемент, след подгрупа - е 0. Тяхната 2, обаче теорема когато п = 1 е вярно (индукция база). Ние предполагаме, че всеки набор от к елементи има 2k подгрупи. Помислете снимачната площадка

Всички подгрупи се разделят на 2 вида. Първият тип otnesom подгрупи, които не съдържат ак + 1. При поемането на такива подгрупи на 2k. Другият подгрупа съдържа ак + 1, и техният брой е равен на 2k, тъй като всеки от тях се получава чрез прибавяне на К + 1 една от подгрупи от първия вид. Всички подгрупи на групата А съдържа:

2k + 2 = 2k х 2k = 2k + 1,

QED.