Viikkotehtävä: osamäärän tekijä (viikko 11/2019)

lukuteoria
kombinatoriikka
#1

Viikkotehtävä

Vastausaikaa su 17.3.2018 klo 24 asti
Vastausaika on päättynyt. Voit keskustella tehtävästä ja sen ratkaisuideoista vapaasti tässä ketjussa.

Tehtävä

Osoita, että luku

\frac{(2^n)!}{1!\,2!\,4!\dotsm(2^{n-1})!}

on jaollinen luvulla

\prod_{k=1}^n \left( 2^{k-1} + 1 \right) = \left(2^0+1\right)\left(2^1+1\right)\dotsm\left(2^{n-1}+1\right).

(Tämä merkintä tarkoittaa tuloa samaan tapaan kuin \sum tarkoittaa summaa. Yhtäläisyysmerkin oikealla puolella on toinen tapa kirjoittaa sama tulo.)

sulki #2
avasi #3
#4

Vinkki: yksi ratkaisu perustuu siihen, että Catalanin luvut ovat kokonaislukuja.

1 Like
#5

Catalanin luvut kannattaa tuntea, koska ne ovat ratkaisu useaan kombinatoriseen laskutehtävään. On tunnettua, että n:s Catalanin luku C_n=\dfrac{1}{n+1}\dbinom{2n}{n} on kokonaisluku (kaava johdetaan esimerkiksi edellä viitatun dokumentin luvussa 4).

Viikkotehtävän ensimmäinen luku on

\frac{(2^n)!}{1!\dotsm(2^{n-1})!} = \prod_{k=1}^n \frac{(2^k)!}{(2^{k-1})!(2^{k-1)}!} = \prod_{k=1}^n \binom{2^k}{2^{k-1}}.

Tämä jaettuna jälkimmäisellä luvulla on

\frac{\prod_{k=1}^n \binom{2^k}{2^{k-1}}}{\prod_{k=1}^n (2^{k-1}+1)} = \prod_{k=1}^n \frac{\binom{2^k}{2^{k-1}}}{2^{k-1}+1} = \prod_{k=1}^n C_{2^k}.

Muita mahdollisia todistusideoita ovat ainakin:

  • \dbinom{2^k+1}{2^{k-1}+1}=\dfrac{2^k+1}{2^{k-1}+1}\dbinom{2^k}{2^{k-1}}
  • \dfrac{1}{2^k+1}\dbinom{2^{k+1}}{2^{k}}=\dbinom{2^{k+1}}{2^k} - \dbinom{2^{k+1}}{2^k-1}