$n$ elemanlı bir kümenin altküme sayısı $2^n$ tanedir.

Question

Kanıt. $n$ üzerine tümevarımla. 

Başlangıç Adımı. $n=0$ için bariz.

Tümevarım Adımı. $n$ için doğru olsun. $n+1$ doğru olduğunu gösterelim. $X=\left\{ a_{1}\ldots ,a_{n+1}\right\}$ ve $Y=\left\{ a_{1}\ldots ,a_{n}\right\}$ olsun. Demek ki $X$'in $a_{n+1}$ elemanını içermeyen $'2^n$ tane ve $a_{n+1}$ elemanını içeren yine $2^n$ tane altkümesi vardır. Yani $X$'in toplamı $2^n+2^n=2^{n+1}$.

Anlamadığım nokta kalın siyah cümle: neden yine ''$a_{n+1}$ elemanını içeren yine $2^n$ tane altkümesi vardır.'' ki?

Comments

http://matkafasi.com/78941/altkumeleri-siralamak

bu lınke baktıktan sonra, su soruyu soralım, o boş daırelerden bırınde oturan ınsanı zaten bılıyorsak gerıye dıger odalara bakmak kalır kı bu da zaten bir eksıgının altkumesayısı demek yanı n+1ıse n tanenın altkume sayısına bakmalı.

---

X in alt kumelerinin tamamini $a_{n+1}$ elemanini icereyen veya icermeyen seklinde 2 farkli grup olarak dusunmus olabilir mi? Daha once bilInen (onceki adim cepte oldugundan) $2^n $ e ek olarak bu kadar daha diyerekten

---

@Anıl Anlamadım. Biraz daha açık olabilir misin?

---

aslında en guclu yontem sızın dedıgınız olan, matbaz hocam. A tane altkumemız olsun ve bu altkumeler n elemandan oluşturulsun, n elemandan bırını cıkarırsak A altkumenın yarısında bu eleman olcak oburlerınde olmucak o zaman n-1 elemanla A/2 altkume oluyor, aynı şekılde n-2 ile A/4 , n-3 ile A/8 dolayısıyla, k eleman ile A altkume oluyorsa   k-i eleman ile $\dfrac{A}{2^i}$ eleman oluyormuş dolayısıyla eger i=k seçersem  0 eleman ile $\dfrac{A}{2^k}$ tane altkume oluyormuş, 0 eleman ile oluşturulacak altkume sayısı 1 oldugundan $1=\dfrac{A}{2^k}\to A=2^k$  gelir ve işimiz biter, bu yontem de cok hoşuma gıttı 

:) 

---

kabere attıgım lınktekı cozum yontemı ıle ve bu son yazılanla ıspatlanır veya, agaç yontemı var onda da bır agac sureklı 2ye dallanarak gıdıyor ve en sonda kaç alt kume oldugu soruluyor algorıtma da şoyle,

Bu eleman kumede mı degıl mı? kumede ıse saga kumede degıl ıse sola gıbı gıbı. ama bunun yerıne bu 2 yontem daha cok hoşuma gıdıyor.


Anlamadıgınız noktaya gelırsem,(pcden yazamadıgım ıcın ıyı yazamıyorum kb.)  n elemanlı kumenın altkume sayısına bakıp bir eleman eksıldıgınde ne olacagını dusunun.

---

@Anıl bir eleman eksilierse $2^{n-1}$ tane altkümesi olur. Bu ne verir bize?

---

matbazın yorumundan sonra yaptıgım yorumdakı taktıgı yapabılmemızı verır, ayrıca senın sorundakı anlamadıgın yerı anlamamızı saglatır, tumevarım yapmak ıcın bundan da ote tekrar edıyorum eger en başta verdıgım lınktekı cevabıma bakmatıysan bakmalısın :) 

---

@Anıl Benim soru kısmındaki kanıtta $X$'in $a_{n+1}$' içermeyen $2^n$ tana altkümesi olduğunu söylüyor, yani bir eleman eksikken. Ama o elemanı eklediğimizde yine $2^n$ tane altkümesi olduğunu söylüyor. Kümeye eleman eklediğimizde altküme sayısında artış olur. Nerde yanlış yapıyorum?

---

@Anıl Baktım.

---

kanıtta yazılanla senın yazdıgın aynı degıl, sen dıyorsunkı $2^n$ altkume varken o elemanı eklesek de aynı altkume sayısı oluyor ama soru kanıtında denılen durum oyle degıl;

$a_{n+1}$ elemanı altkumelerın hepsıne aıt oldugunda $2^n$ var ve $a_{n+1}$ hiçbir altkumede olmadıgında gene $2^n$ var dolayısıyla bu 2 altkumeleri birleştirirsek $2^n+2^n=2^{n+1}$ oluyor kı bu da ıstedıgımız şey.

---

bu kanıtlar kafa karıştırıyor oyuzden obur ıspatları siddetle onerıyorum.

---

 {${a_{n+1}}$} kumesinin $ a_{n+1}$ elemanini icermeyen diger tum kumelerle ayri ayri birlesimi onceki listeden farkli ama ayni sayida kume belirIir. Demek istedigi 1 fazla elemani eklediginde ayni sayida alt kume oldugu degil ,n+1 elemanli yeni kumenin eklenen elemani iceren alt kume sayisinin $2^n $ oldugu

---

Bir sonlu kümenin herhangi bir elemanını bulunduran alt küme sayısı, o elemanı bulundurmayan alt küme sayısına eşittir. $X$ in $a_{n+1} $ elemanını bulunduran alt kümelerinin sayısı: $2^n$, ve bulundurmayan alt kümelerinin sayısı: $2^n$ adettir. Demek ki $X$ 'in $2^n+2^n=2.2^n=2^{n+1}$ tane alt kümesi vardır.

Answer 1

$A$ kumesi $a_{n+1}$ elemaninin iceren $X$ kumesinin bir alt kumesi olsun. Bu durumda $$A\setminus \{a_{n+1}\}$$ kumesi $Y$ kumesinin bir alt kumesi olur.Demek ki $2^{n}$ tane secenek varmis.

Bunlarin hepsi icin de ayri ayri kumeler elde ederiz. $B,C$ kumeleri $Y$ kumesinin farkli alt kumeleri ise $$B \cup \{a_{n+1}\} \ne C \cup \{a_{n+1}\} $$ olur. 

Answer 2

$$(x+y)^n=\sum_{k=0}^n \binom{n}{k}x^{n-k}y^k$$

$x=1$,   $y=1$  alinirsa

$$2^n=\sum_{k=0}^n \binom{n}{k}=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\dots+\binom{n}{n}$$

$$\underbrace{\binom{n}{0}}_{\text{0 elemanli alt kume sayisi}}+\underbrace{\binom{n}{1}}_{\text{1 elemanli alt kume sayisi}}+\underbrace{\binom{n}{2}}_{\text{2 elemanli alt kume sayisi}}+\dots+\underbrace{\binom{n}{n}}_{\text{n elemanli alt kume sayisi}}$$

$$2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\dots+\binom{n}{n}$$

Comments

Soru bunu sormuyor sanki. Siyah yerin neden dogru oldugunu soruyor.