Kusurabakma abi, yorumları yazdıktan sonra adam gibi vaktım olmadı.
Motivasyon:
Kombinasyon diyorki (kombinasyonu nasıl ispatlarız şuanda konumuz degil sanırım) elimde
x adet farklı eleman varsa bu elemanlardan
a<x tanesini seçip bir küme oluşturcaksam bu kümenin eleman sayısı
(xa)=x!a!(x−a)! tane olur.
Şimdi 2-d düzlemdeyiz farklı 3 A,B,C noktası seçtim. A'dan B'ye 2, B'den C'ye 3 yol var, bağımlı olaylarından dolayı, A'dan C'ye tam olarak 6 farklı yol seçebiliriz.
Seçim ve bağımsızlığı n basamaklı sayı yazmak için kullanalım.
Varsayım: 2-d düzlemde n+1 farklı nokta alalım
a_1,a_2,...,a_{n+1} şimdi her ardışık
a_i noktası arasında tamı tamına 10 tane yol olsun, Her yol, kaçıncı olduğuna bağlı olarak
\mod 10'da birbirine denk olsun(yani misal bir f fonksiyonu
a_3-a_4 arasındaki 10 farklı yolla,
a_7-a_8 arasındaki 10 farklı yolu birebir ve örten şekilde eşliyor). Her ardışık 2li nokta arası yollar diğer ardışık 2li noktaların yollarına bağımlı olduğundan
a_1'den
a_{n+1}'e kadar toplam
10^n farklı yol varmış deriz,
Tümevarım kullanarak ispat.(tümevarım için ise sadece 1. adımın kullanılması yetiyor, çünkü diğer adımlar için ilk yollar kaldırıldıgı zaman zaten ilk sisteme eş sistem elde ediyoruz.)
şimdi geldi her 2 ardışık nokta arasında tanımladığımız 10lu yollardaki her biricik yolun eşit sayıda kullanıldığını göstermek bunun için a_1-a_2 ve a_2-a_{n+1} noktalarına bakalım, a_1-a_2 arasında 10 tane yol vardı bunlara y_{1,1},y_{1,2},...,y_{1,10} diyelim, a_2-a_{n+1} arasındaki farklı yolların sayısına ise \gamma_{n-1} kadar diyelim. y_{1,1} yolunu ve \gamma_{n-1} yolunu kullanmakla y_{1,2} yolunu ve \gamma_{n-2} yolunu kullanmak aynı sayıda olduğundan tümevarımın 1. adım için herşey yolunda, şimdi 2. adım olarak ilk yolları ortadan kaldırıp aynısını geri kalan n nokta için uygulayalım, ilk adımdaki sonuç burada dageçerli olur. şimdi ilk k<n yolu kaldırıp tümevarım varsayımımızı kabul edip, ilk k+1<n yolun kaldırılmış haline bakalım, ilk sonucu kullanarak, a_k-a_{k+1} arasındaki her yolun gene eşit kullanıldığı ve a_{k+1}-a_{n+1} arasındaki yolların önemi olmadığı gözükür.
Not: Farklı bir yol diye yazdım, istenilen şekildeki basit tümevarım ispatını da yazacagım, eğer neye tümevarım uygulayacagımı tam kavrarsam.