Matematiksel tümevarım

Matematiksel tümevarım, matematiksel bir gerçeği kanıtlamanın özel bir yoludur. Bir şeyin tüm doğal sayılar (tüm pozitif tam sayılar) için doğru olduğunu kanıtlamak için kullanılabilir. Buradaki fikir şudur

• İlk durum için doğru olan bir şey var
• Aynı şey bir sonraki vaka için de her zaman geçerlidir

sonra

• Aynı şey her vaka için geçerlidir

Matematiğin dikkatli diliyle:

• İspatın n {\displaystyle n} üzerinden tümevarım yoluyla yapılacağını belirtin. (n {\displaystyle n} tümevarım değişkenidir).
• İfadenin n {\displaystyle n} 1 olduğunda doğru olduğunu gösterin.
• İfadenin herhangi bir n doğal sayısı için doğru olduğunu varsayalım {\displaystyle n} . (Buna tümevarım adımı denir.)
• O halde ifadenin bir sonraki sayı olan n + 1 {\displaystyle n+1} için de doğru olduğunu gösterin.

Çünkü 1 için doğrudur, o zaman 1+1 için doğrudur (=2, tümevarım adımıyla), o zaman 2+1 için doğrudur (=3), o zaman 3+1 için doğrudur (=4) ve bu böyle devam eder.

Tümevarım yoluyla kanıtlamaya bir örnek:

Tüm n doğal sayıları için şunu kanıtlayın:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)}

Kanıt:

İlk olarak, ifade şöyle yazılabilir: tüm n doğal sayıları için

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)}

n üzerinde tümevarımla,

İlk olarak, n=1 için:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} ,

Yani bu doğru.

Ardından, bazı n=n₀ için ifadenin doğru olduğunu varsayalım. Yani,:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}

Sonra n=n için₀ +1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}

yeniden yazılabilir

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) olduğundan, {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),}

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}

Dolayısıyla kanıt doğrudur.