równość rekurencyjna do pokazania

[matinf]

Witam,

Niech a n oznacza liczbę uporządkowanych podziałów \(\displaystyle{ n}\)-zbioru, w których kolejność
elementów w bloku jest bez znaczenia, natomiast istotna jest kolejność bloków (np.\(\displaystyle{ a_2 = 3}\):
\(\displaystyle{ \left\langle \left\{ 1,2\right\} \right\rangle \left\langle \left\{ 1\right\},\left\{ 2\right\} \right\rangle \left\langle \left\{ 2\right\},\left\{ 1\right\} \right\rangle}\)

(a) Udowodnij, że ciąg spełnia zależność rekurencyjną.
\(\displaystyle{ a_n = \sum_{i=0}^{n-1} {n\choose i} a_i \ \ \ \ \ a_1 = 0}\)
I teoretycznie jest to dość intuicyjne. Aczkolwiek chciałbym podjąć próbę indukcyjnego dowodu, ale sprawia mi to trudność:
Wezmę założenie po prostu:
\(\displaystyle{ a_n = {n\choose 0} a_0 + {n\choose 1} a_1 + ... + {n\choose n} a_n}\)
Teza":
\(\displaystyle{ a_{n+1} = {n+1\choose 0} a_0 + {n+1\choose 1} a_1 + .... + {n+1\choose n} a_n =\\a_0 \left( {n \choose 0}+{n \choose -1}\right) + a_1\left({n\choose 1} + {n\choose 0} \right) + ... + a_n \left({n\choose n} + {n\choose n-1} \right)}\)
Ostatecznie dojdę do czegoś takiego:

\(\displaystyle{ a_{n+1} = a_1{n \choose 0} + a_2 {n\choose 1} + ... + a_n(n+1)}\)
I nie bardzo wiem jak mam to interpretować. Proszę o pomoc

[kerajs]

Póżna porą pisałeś ten post

\(\displaystyle{ a_n = {n\choose 0} a_0 + {n\choose 1} a_1 + ... + {n\choose n} a_n}\)

Raczej
\(\displaystyle{ a_n = {n \choose 0} a_0 + {n\choose 1} a_1 + ... + {n\choose n-1} a_{n-1}}\)

\(\displaystyle{ a_{n+1} = {n+1\choose 0} a_0 + {n+1\choose 1} a_1 + .... + {n+1\choose n} a_n =\\a_0 \left( {n \choose 0}+{n \choose -1}\right) + a_1\left({n\choose 1} + {n\choose 0} \right) + ... + a_n \left({n\choose n} + {n\choose n-1} \right)}\)

Dwumian \(\displaystyle{ {n \choose -1}}\) jest troszkę problematyczny.

Pomijając powyższe pomyłki wynikające pewnie ze zmęczenia masz

\(\displaystyle{ a_n = \sum_{i=0}^{n-1} {n\choose i} a_i \ \ \ \ \ a_1 = 0}\)

czyli
\(\displaystyle{ a _{2} = {2\choose 0} a _{0} +{2\choose 1} a _{1} =1 \cdot a _{0}+2 \cdot 0 \neq 3=a _{2}}\)
Tu aby spełnić sumę powinno być: \(\displaystyle{ a _{0}=1}\)
Wtedy \(\displaystyle{ a _{1}= {1 \choose 0}a _{0}=1}\)
\(\displaystyle{ a _{2} = {2\choose 0} a _{0} +{2\choose 1} a _{1} =1 \cdot 1+2 \cdot 1= 3}\)
I byłoby OK gdyby nie zbiór pusty który jest uwzgledniany dla \(\displaystyle{ a _{0}}\) , a dla kolejnych \(\displaystyle{ a _{n}}\) jest pomijany.
Jaka jest oryginalna treść zadania?

[matinf]

Tak, oczywiscie się pomyliłem wielokrotnie.
Treść powinna być taka, że \(\displaystyle{ a_0 =1}\)

I dalej podbijam ten temat. Jak to w końcu pokazac ?

[Zordon]

Dowodu indukcyjnego nie wyciśniesz w żaden sposób poprzez "przekształcanie wzorków". Musi być jakieś rozumowanie kombinatoryczne. Przykładowo: ile jest podziałów, w których element \(\displaystyle{ n}\) ląduje w zbiorze mocy \(\displaystyle{ n-i}\)?

[matinf]

Dowodu indukcyjnego nie wyciśniesz w żaden sposób poprzez "przekształcanie wzorków".

A no właśnie. Spodziewałem się, że indukcja tutaj nie pójdzie.
Czyli jedyna szansa to interpretacja kombinatoryczna. A może funkcje tworzące ? Osobiście myślę, że funkcje tworzące tutaj to rzecz "niebanalna".

Musi być jakieś rozumowanie kombinatoryczne. Przykładowo: ile jest podziałów, w których element \(\displaystyle{ n}\) ląduje w zbiorze mocy \(\displaystyle{ n-i}\)?

Przemyślę to wnet.-- 1 sie 2014, o 21:49 --

ile jest podziałów, w których element \(\displaystyle{ n}\) ląduje w zbiorze mocy \(\displaystyle{ n-i}\)?

No to spróbuję odpowiedzieć:
\(\displaystyle{ {n-1 \choose n - i - 1} \cdot a_{i} = {n-1 \choose i} \cdot a_{i}}\)
gdzie \(\displaystyle{ a_i}\) oznacza liczbę podziałów zbioru \(\displaystyle{ i}\)-elementowego.

I oczywiście będzie iteracja sumy po tym wzorku.
\(\displaystyle{ \sum_{i=1}^{n-1} {n-1 \choose i} \cdot a_{i}}\)

Takie coś otrzymałem, ale właśnie. Nie wiele mi to mówi. Może coś źle wymyśliłem ?