$n$ tane elemanı olan bir kümenin tam $n$ tane $n-1$ elemanlı altkümesi olduğunu kanıtlayın.

Question

 Tümevarımla kanıtlamaya çalıştım (ama olmadı). Yani,

  $n>1$ durumu için inceleyeceğim. O zaman,

 $n=2$ için doğru. Yani, 2 elemanı olan bir kümenin tam 2 tane 1 elemanlı altkümesi vardır, gayet açık.

 $n$ için doğru olduğunu varsayıp, $n+1$ için kanıtlayalım.

 Bundan sonraki adımları için yardım edebilir misiniz, ayrıca farklı bir yöntemle kanıt varsa ipucu verebilir misiniz?

Comments

n-1 elemanlı alt kümeler 1 elemanlı tümleyenleri ile birebir eşleşir. Aslında bu direkt cevabı verir.

---

Ya da $C(n,n-1)=n$ dir.

---

Benim yorumum da $C(n,n-1)=C(n,1)$'e denk geliyor. Ne tarz bir ispat istedigimize de bagli tabi. Isin icine $C(n,k)$ girince (temel) kombinatorik bir ispat oluyor. Ne tarz ispat isteniyor?

---

<p>O zaman, $C$$(n,n-1)=n$ doğru olduğunu göstermeliyiz. Peki, nasıl gösterebiliriz?
</p>

---

ilk yorumum bu cevabi veriyor zaten.

---

O zaman şöyle sorarsam eğer, n-1 elemanlı altkümeler 1 elemanlı tümleyenleriyle birebir neden eşleşir?''

---

Tamam şimdi anladım, teşekkürler.

---

 Peki soruyu tümevarımla kanıtlayabilir miyiz?

---

Evet. $n+1$'i iceren $n$ elemanli kumeler tumevarim basamagindan gelir. Icermeyen de bir adet var.

---

Peki. $n$ tane  elemanı olan bir kümenin kaç tane $n-2$ elemanlı altkümesi vardır? Diye sorsam. $C(n,n-2)$ tane vardır, değil mi?

---

 Ayrıca, bir önceki sorumda tümevarımla gösterebileceğimizi söylemiştiniz. Gösteremedim. Açık bir şekilde yazabilir misiniz?

---

@bilgeee tumevarim cok kulanisli bir yontem degil gibi duruyor burada. Ama illaki tumevarim istiyorsan soyle yapabilirsin:

$\{a_1, a_2, \ldots, a_n \}$ kumesinin $n$ tane $n-1$ elemanli kumesi oldugunu kabul edelim. $\{a_1, a_2, \ldots, a_n , a_{n+1}\}$ kumesinin $n+1$ tane $n$ elemanli kumesi oldugunu gosterecegiz.

$a_{n+1}$ elemanini disariya alirsak eger geri kalan elemanlar $n$ elemanli bir altkume olustururlar. Buradan $+1$ katki saglariz. Simdi geriye kalan elemanlarin olusturdugu bu $n$ elemanli altkumenin tam $n$ tane $n-1$ elamanli altkumesi oldugunu biliyorum. Bunlarin her birine teker teker $a_{n+1}$ elamanini eklersem, elde ettigim kume $n$ elemanli olur. Buradan da $+n$ katki aliriz.

Cok guzel bir Turkce ile yazamadim ama Sercan'in bir onceki yorumda soyledigi sey tam olarak bu. 

---

Teşekkürler.