$\binom{2^n-1}{k}$ sayısı her zaman tek midir?

Question

$n$ bir pozitif tam sayi ve $0\le k \le 2^n-1$ de bir tam sayi olmak uzere  $$\displaystyle\binom{2^n-1}{k}$$ her zaman tek bir sayi midir?

Answer 1

Pascal üçgenini düşünelim.Pascal üçgeninde her satırdaki sayı, üst satırdaki en yakın iki sayının toplamıdır. (Yani: $\binom{m}{k}=\binom{m-1}{k-1}+\binom{m-1}{k}\ (0<k<m)$ için), 

$\binom{2^n}{k}$ nın, $(0<k<2^n)$ için, çift olduğu ($k$ da yeterince 2 nin kuvveti olmadığından)  kolayca görülür. Pascal üçgeninde bu satır 1 çift çift çift çift .....çift 1 şeklindedir.

($\binom{2^n-1}{0}=\binom{2^n-1}{2^n-1}=1$ olduğu zaten açıktır.)

$\binom{2^n}{1}=\binom{2^n-1}{0}+\binom{2^n-1}{1}=1+\binom{2^n-1}{1}$ olduğu için $\binom{2^n-1}{1}$ tek olmalıdır.

Daha sonra $\binom{2^{n}}{2}=\binom{2^n-1}{1}+\binom{2^n-1}{2}$ den $\binom{2^n-1}{2}$nin tek olduğu benzer şekilde görülür. 

Bu şekilde, devam edilerek $\binom{2^n-1}{k}\ (0<k<2^n-1)$ nin tek sayı olduğu elde edilir.  

Comments

$2^{n-1}$'ler $2^n-1$ olmali, galiba.

---

Teşekkürler, düzelttim.

Answer 2

Ben de bugun bir ispatla ugrasirken dusundum bu cikarimi ve dogru olacagina inandim. Ispatini da yaptim. Benim ispatim da su sekilde:

Kullandigim: $a$ ile $2^k-a$ sayilarini tam bolen maksimum $2$ kuvveti aynidir. 

Ispati:  (aşırı dolambaçsız bir şekilde)
$2^b \mid a$ ise $2^k-a=2^k-2^ba_1=2^b(2^{k-b}-a_1)$ olur.
$2^c \mid (2^k-a)$ ise $a=2^k-(2^k-a)$ da $2^c$ sayisina tam bolunur.

Tabi burada $b,c \le k$ olacagi bariz. Bu cikarim bize binom aciliminda hic $2$'nin kati olamayacagini verir.

Answer 3

$\sum_{k=0}^{2^n-1}\displaystyle\binom{2^n-1}{k}=\displaystyle\binom{2^n-1}{0}+\displaystyle\binom{2^n-1}{1}+\displaystyle\binom{2^n-1}{2}+...+\displaystyle\binom{2^n-1}{2^n-1}$ toplamında $2^n$ sayıda terim bulunmaktadır.Toplam:

$\sum_{k=0}^{2^n-1}\displaystyle\binom{2^n-1}{k}=2^{2^n-1}$ olup çift bir sayı olduğundan ya tüm terimler çift,ya tüm terimler tek, ya da en az iki terim çifttir. İlk terim tek olduğundan tüm terimlerin çift olma durumu mümkün değildir. O zaman, ya tüm terimler tektir ya da en az iki terim çifttir.  Bu toplamın herhangi bir terimi $0\leq k\leq2^n-1$ olmak üzere $\displaystyle\binom{2^n-1}{k}$ olsun. $\displaystyle\binom{2^n-1}{k}=\frac{(2^n-1)(2^n-2)(2^n-3)...(2^n-k)}{k!}$ bu ifadenin hem payında hemde paydasında eşit sayıda $2$ çarpanı vardır(?), dolayısıyla sadeleşmeden sonra iki tek sayının birbirine bölümü kalır. Bölüm tek sayı olacaktır. Böylece toplamdaki her bir terimin tek olduğu söylenebilir.

Comments

"Ya tüm terimler tektir, ya da en az iki terim çifttir." Bu dogru bir cikarim fakat nerede kullandik?


"$\displaystyle\binom{2^n-1}{k}=\frac{(2^n-1)(2^n-2)(2^n-3)...(2^n-k)}{k!}$ bu ifadenin hem payında hemde paydasında eşit sayıda $2$ çarpanı vardır(?)" sorunun dengi bu zaten hocam. Tek olmasi pay ve paydadaki $2$'nin kuvvetlerinin esit olmasi gerek. Cevap soruyu kabul etmis olmuyor mu bu durumda? Cunku soru da "hem payinda hem paydasinda esit $2$ carpani var mi?".

---

İşte işin en önemli yerine bende biraz da yorulduğum için "?" koydum. Bana biraz uzun ve sıkıcı gibi geldi bıraktım. Elbetteki açıklanması,gösterilmesi gerekiyor. Belki bu kısmı siz yaparsınız:))