Induktion

Antingen skriva ut den kombinatoriska symbolen i fakultetsnotation eller använda kombinatoriska identiteter såsom Pascals identitet https://sv.wikipedia.org/wiki/Pascals_identitet vilken ser lovande ut här. 

SeriousCephalopod skrev:

Antingen skriva ut den kombinatoriska symbolen i fakultetsnotation eller använda kombinatoriska identiteter såsom Pascals identitet https://sv.wikipedia.org/wiki/Pascals_identitet vilken ser lovande ut här. 

Hur ska man använda Pascals identitet? Alltså hur kommer uttrycket se ut när jag stoppar in mina värden som jag har? :) 

I induktionssteget behöver du jobba med

${{2(n + 1)} \choose {n + 1}}$

och då kanske det är användbart att använda kombinatoriska identiteter som såsom Pascals identitet för att skriva om uttrycket att du får uttryck på formen ${2m} \choose m$ med mindre $m$ då du kan utnyttja att du då vet att de är mindre än $2^{2m - 2}$. 

Normala induktionstekniker så jämför med tidigare problem du läst och ta i alla fall och försök en vända först. 

Hej!

En mängd $M$ som består av $2n$ stycken element har $2^{2n}$ stycken delmängder, varav tomma mängden är en och mängden M själv är en. 

Det finns ${2n \choose n}$ stycken delmängder som innehåller $n$ stycken element. Detta antal är uppenbarligen mindre än det totala antalet delmängder till M, så det gäller att

    ${2n \choose n} < 2^{2n}.$

Det du vill visa är att

    $4\cdot {2n \choose n} < 2^{2n}$

om $M$ har åtminstone $10$ element.

SeriousCephalopod skrev:

I induktionssteget behöver du jobba med

${{2(n + 1)} \choose {n + 1}}$

och då kanske det är användbart att använda kombinatoriska identiteter som såsom Pascals identitet för att skriva om uttrycket att du får uttryck på formen ${2m} \choose m$ med mindre $m$ då du kan utnyttja att du då vet att de är mindre än $2^{2m - 2}$. 

Normala induktionstekniker så jämför med tidigare problem du läst och ta i alla fall och försök en vända först. 

Är det rätt om jag börja så här: 

(n k) = n!/(n-k)!*k!

(2n n) = 2n!/(2n-n)!*n!

(2n n) = 2n!/n!*n!

SeriousCephalopod skrev:

Antingen skriva ut den kombinatoriska symbolen i fakultetsnotation eller använda kombinatoriska identiteter såsom Pascals identitet https://sv.wikipedia.org/wiki/Pascals_identitet vilken ser lovande ut här. 

Jag tänkte faktiskt använda den kombinatoriska symbolen i fakultetsnotation och jag  har kommit så här långt:

$2n!$ betyder inte $2(n!)$. Det betyder $(2n)!$ dvs produkten av alla heltal mindre och lika med 2n. 

Det går inte att förkorta bort $n!$ så enkelt ur detta uttryck som att det vore en faktor. 

$\frac{2n!}{n!} = \frac{2n \cdot (2n - 1) \cdots (n + 1)n(n - 1) \dots 2 \cdot 1}{n(n - 1) \dots 2 \cdot 1}= {2n \cdot (2n - 1) \cdots (n + 1)}$

SeriousCephalopod skrev:

$2n!$ betyder inte $2(n!)$. Det betyder $(2n)!$ dvs produkten av alla heltal mindre och lika med 2n. 

Det går inte att förkorta bort $n!$ så enkelt ur detta uttryck som att det vore en faktor. 

$\frac{2n!}{n!} = \frac{2n \cdot (2n - 1) \cdots (n + 1)n(n - 1) \dots 2 \cdot 1}{n(n - 1) \dots 2 \cdot 1}= {2n \cdot (2n - 1) \cdots (n + 1)}$

Ja det är sant....Vad är nästa steg?Blir tacksam om någon svarar!

Jag har kommit i mina basfall men det visar sig att VL blir mindre än HL. Så det är sant! 

Vitsen med induktionsteget är att du ökar $k \to k + 1$ men effekten av detta är att $2k$ i binomialkoefficienten byts mot $2(k + 1) = 2k + 2$ inte $2k + 1$ i uttrycket.  Steget görs på k, inte på placeringen his k + 1.

${{2(k + 1)}\choose{k+1}} = {{2k + 2}\choose{k+1}}$

Jag ser heller inte att du faktiskt börjar försöka lösa problemet mer än bara skriva upp hälften av problemställningen. Att andra vill att du redovisar hur du har försökt handlar inte om att de (jag) försöker vara jobbiga utan eftersom det ger en inblick i vad du behöver för förklaringar om så att vägledningen kan bli så konstruktiv som möjligt. Är det så att du inte vet hur man gör induktionssteg vid olikheter utan endast vid likheter? Är det så att du inte vet så många identiteter som gäller för binomialkoefficienten? Är det mekaniska operationer med fakultet så inte är bekant? Osv.

Iochmed att jag inte ser något direkt avslut på denna kedja så ger jag ett exempelbevis för induktionsstegsdelen: 

Jag tänker att man i induktionssteget applicerar Pascals identitet två gånger (praktiskt sett så minskar övre och nedre tal med 1):

EDIT: Denna rad har skrivfel i sig. Korrigeras 12:15

Dvs

${{2k + 2}\choose{k+1}} = 2{{2k}\choose{k}} + {{2k}\choose{k- 1}} + {{2k}\choose{k+ 1}}$

Sedan får man börja introducera olikheter

${{2k} \choose {k + 1}} = {{2k} \choose {k - 1}} < {{2k} \choose {k}}$

bör vara bekant, dvs att "centrala koefficienten" är störst --  annars får det bevisas separat. 

Därmed har vi 

Här tillämpar vi att vi redan vet att ${{2k}\choose{k}} < 2^{2k - 2}$ så 

${{2k + 2}\choose{k+1}} < 2^2 {{2k}\choose{k}} < 2^2 \cdot 2^{2k - 2} = 2^{2(k + 1) - 2}$

Vilket skulle bevisas. 

Det går nog att göra motsvarande bevis i fakultetsnotation men när det kommer till kombinatoriska identiteter så är det generellt enklast att antigen 1. Använda kombinatoriska identiteter, 2. Använda genererande polynom, eller 3. Använda strikt kombinatoriska argument via konstruktioner av mängder. 

Försök gärna få fakultetsmetoden att fungera och presentera den här. 

EDOT ¤%&¤%# 2019 och TeX fungerar fortfarande inte.