Przykład udowodnienia częściowej i całkowitej poprawności algorytmu sumy ciągu z liczbami metoda matematycznej indukcji.

// Vladimir Poplavskij. Wykladowca
// Suma n liczb całkowitych
// 2022-10-22

SumNatural(n) {
  sum = n * (n + 1) / 2;
  return sum;
}
                       

• Udowodnij wzór na najmniejszą liczbę, która może być użyte w danym oświadczeniu.
• Załóżmy, że to prawda dla dowolnej liczby $ n $.
• Użyj poprzednich kroków, aby udowodnić, że jest to prawda dla następnej liczby $ n + 1 $.

$$ \sum_{i=1}^{n} i = \frac{n(n + 1)}{2} $$

• Czy to jest prawdziwe dla $ n = 1 $? Tak, $ \frac{1(1 + 1)}{2} = 1$
• Załóżmy, że działa dla $ n $
• Udowodnij, że to prawda, gdy $ n $ jest zastąpione przez $ n + 1 $

Zaczniemy od $ n $:

$$ \sum_{i=1}^{n} i = \frac{n(n + 1)}{2} \\ $$ $$ 1 + 2 + 3 + ... + (n - 1) + n = \frac{n(n + 1)}{2} \quad \mbox{przekształcamy lewa strona równania}\\ \\ $$ $$ 1 + 2 + 3 + ... + ((n + 1) - 1) + (n + 1) = \frac{(n + 1)[(n + 1) + 1]}{2} \quad \mbox{zameniamy $ n $ na $ n + 1 $}\\ \\ $$ $$ 1 + 2 + 3 + ... + n + (n + 1) = \frac{(n + 1)(n + 2)}{2} \quad \mbox{spraszamy}\\ \\ $$ $$ (1 + 2 + 3 + ... + n) + (n + 1) = \frac{(n + 1)(n + 2)}{2} \quad \mbox{regrupujemy lewa strona}\\ \\ $$ $$ \frac{n(n + 1)}{2} + (n + 1) = \frac{(n + 1)(n + 2)}{2} \quad \mbox{zameniamy w lewej stronie na (przypuszczalna) formula z #2}\\ \\ $$ $$ \frac{n(n + 1)}{2} + \frac{2(n + 1)}{2} = \frac{(n + 1)(n + 2)}{2} \quad \mbox{ustanowimy wspólny mianownik}\\ \\ $$ $$ \frac{n(n + 1) + 2(n + 1)}{2} = \frac{(n + 1)(n + 2)}{2} \quad \mbox{uspraszamy}\\ \\ $$ $$ \frac{(n + 1)(n + 2)}{2} = \frac{(n + 1)(n + 2)}{2} \quad \mbox{Wyjmij wspólny dzielnik $n + 1$}\\ \\ $$

Udowodniliśmy, że wzór obowiązuje dla n + 1.

Podsumowanie.

• Czy to jest prawdziwe dla $ n = 1 $? Tak, $ \frac{1(1 + 1)}{2} = 1$
• Załóżmy, że działa dla $ n $
• Udowodnij, że to prawda, gdy $ n $ jest zastąpione przez $ n + 1 $