Przedstawienie liczby naturalnej

[patryk00714]

Wykazać, że każdą liczbę naturalną da się jednoznacznie przedstawić w postaci \(\displaystyle{ n= \sum_{i=1}^{k}d_i i!=d_1 \cdot 1!+d_2 \cdot 2!+...+d_k \cdot k!}\),

gdzie \(\displaystyle{ d_i \in \mathbb{N} \cup \left\{ 0\right\} \qquad d_i \le i \qquad 1 \le i \le k}\)

Proszę o pomoc.

[jutrvy]

No pewnie, że można! \(\displaystyle{ d_1 = n}\), \(\displaystyle{ d_i = 0, \ \hbox{gdy} \ n > 1}\).

Ale przedstawienie nie jest jednoznaczne, np dla \(\displaystyle{ n = 8}\), bo może być \(\displaystyle{ 8 = 2! + 3!}\), ale może też być \(\displaystyle{ 8 = 8\cdot 1!}\), a może też być \(\displaystyle{ 8 = 4\cdot 2!}\).

Jesteś pewien, że tak brzmi treść tego zadania?

[patryk00714]

Powtarzam \(\displaystyle{ d_i \le i}\)

[jutrvy]

Ok, masz rację - głupi jestem.

1. Istnienie.

Dowód przez indukcję.

Dla \(\displaystyle{ n=1}\) nie ma czego dowodzić.

Ustalmy \(\displaystyle{ n>0}\) i załóżmy, że teza zachodzi dla każdego \(\displaystyle{ n^{\prime} < n}\).

Jeśli \(\displaystyle{ n-1}\) jest parzysta, to znaczy, że w rozkładzie \(\displaystyle{ n-1}\) współczynnik \(\displaystyle{ d_1 = 0}\). Wtedy

\(\displaystyle{ n = 1 + \sum_{i=2}^{k}d_ii!}\), czyli po prostu zwiększamy pierwszy współczynnik.

Jeśli \(\displaystyle{ n-1}\) jest nieparzysta, to znaczy, że w rozkładzie \(\displaystyle{ n-1}\) współczynnik \(\displaystyle{ d_1 = 1}\). Ponieważ dla \(\displaystyle{ i \ge 2}\) wszystkie \(\displaystyle{ i!}\) są parzyste, więc musimy wyzerować współczynnik przy jedynce i zwiększyć o jeden \(\displaystyle{ d_2}\). Może się to okazać niemożliwe (może przecież być, że \(\displaystyle{ d_2 = 2}\)). Wtedy robimy tak, że zerujemy współczynnik \(\displaystyle{ d_2}\) i zwiększamy \(\displaystyle{ d_3}\) o jeden (bo chodzi nam o to, żeby zwiększyć sumę o jeden, a jeżeli odjęliśmy od tej sumy \(\displaystyle{ 1 + 2\cdot 2!}\), to chcemy dodać liczbę o jeden większą, czyli \(\displaystyle{ 3!}\)). Ogólnie - dla dowolnego \(\displaystyle{ i}\), jeśli \(\displaystyle{ d_i = i}\), to zerując \(\displaystyle{ d_i}\) i zwiększając \(\displaystyle{ d_{i+1}}\) o jeden zwiększam całą sumę o \(\displaystyle{ i!}\) (bo zabieram \(\displaystyle{ i\cdot i!}\) ale dodaję \(\displaystyle{ (i+1)! = (i+1)\cdot i!}\), bo zwiększam o jeden \(\displaystyle{ d_{i+1}}\)), ale ponieważ w poprzednich krokach w sumie z sumy zabrałem

\(\displaystyle{ \sum_{m=1}^{i}m\cdot m! = (i+1)! - 1}\), to jeśli znajdziemy takie \(\displaystyle{ d_i}\), że \(\displaystyle{ d_i < i}\), to wykonując ten algorytm (tu będzie skończenie wiele kroków) dojedziemy do tego, że zwiększymy naszą sumę o jeden i otrzymamy nowy rozkład. Jeżeli natomiast dla każdego \(\displaystyle{ i \le k}\) zachodzi \(\displaystyle{ d_i = i}\), to kiedy dojdziemy do \(\displaystyle{ d_k}\) i okaże się, że \(\displaystyle{ d_k = 0}\), to wtedy zwiększamy \(\displaystyle{ d_{k+1}}\) o jeden i mamy, że \(\displaystyle{ n = (k+1)!}\).

Jest już późno - jedyność napiszę jutro, ok?

[bakala12]

To może ja dorzucę dowód że rozkład jest jednoznaczny.
Załóżmy, nie wprost, że istnieją co najmniej dwa różne rozkłady pewnej liczby \(\displaystyle{ n}\) w postulowanej postaci. Weźmy dowolne dwa z nich:
\(\displaystyle{ n=\sum_{i=1}^{m}d_{i}\cdot i! = \sum _{i=1}^{m'} d_{i}'\cdot i!}\)
przy czym bez straty ogólności rozważań \(\displaystyle{ m \le m'}\) i oczywiście \(\displaystyle{ d_{m},d_{m'}'\neq 0}\).
Rozważmy najpierw przypadek \(\displaystyle{ m<m'}\). Wówczas otrzymujemy:
\(\displaystyle{ 0=\sum_{i=1}^{m'}d_{i}'\cdot i! - \sum _{i=1}^{m} d_{i}\cdot i!=\underbrace{\sum_{i=m+1}^{m'}d_{i}'\cdot i!}_{S_{1}} -\underbrace{ \sum_{i=1}^{m}\left(d_{i}-d_{i}' \right)\cdot i!}_{S_{2}}}\)
Ponadto mamy:
\(\displaystyle{ \forall i \quad d_{i}-d_{i}' \le i}\) a zatem:
\(\displaystyle{ S_{2} \le \sum_{i=1}^{m} i \cdot i! = \sum_{i=1}^{m}\left[\left(i+1\right)!-i!\right]=\left(m+1\right)!-1!<\left(m+1\right)! \le \sum_{m+1}^{m'} d_{i}'\cdot i!=S_{1}}\) (bo \(\displaystyle{ d_{m'}' \neq 0}\))
co oznacza sprzeczność z równością wyżej. Zatem \(\displaystyle{ m=m'}\). Oznaczmy teraz przez \(\displaystyle{ j}\) największy taki indeks ze zbioru \(\displaystyle{ \left\{ 1,2,\dots, m\right\}}\) dla którego zachodzi \(\displaystyle{ d_{j}' \neq d_{j}}\) (takie \(\displaystyle{ j}\) istnieje bo założyliśmy, że rozkłady nie są identyczne). Nie tracąc ogólności rozumowania weźmy \(\displaystyle{ d_{i}'>d_{i}}\). Wówczas otrzymujemy:
\(\displaystyle{ 0=\sum_{i=1}^{m}\left(d_{i}'-d_{i}\right)\cdot i!=\sum_{i=1}^{j} \left(d_{i}'-d_{i}\right)= \underbrace{\left(d_{j}'-d_{j}\right)\cdot j! }_{S_{1}} - \underbrace{\sum_{i=1}^{j-1}\left(d_{i}-d_{i}'\right)\cdot i!}_{S_{2}}}\)
Wówczas podobnie jak wcześniej mamy:
\(\displaystyle{ S_{2} \le \sum_{i=1}^{j-1} i \cdot i!=\sum_{i=1}^{j-1}\left[\left(i+1\right)!-i!\right]=j!-1!<j!\le \left(d_{j}'-d_{j}\right)\cdot j!=S_{1}}\)
Co przeczy uzyskanej wyżej równości.
Dowodzi to, że rozkład w postulowanej postaci jest jednoznaczny.
Już po napisaniu tego wszystkiego dostrzegam, że oddzielna analiza przypadku \(\displaystyle{ m<m'}\) nie jest potrzebna, bo to można zrobić identycznie jak \(\displaystyle{ m=m'}\), ale już nie będę tego poprawiał

[a4karo]

Prostszy dowód jest taki:
niech twierdzenie będzie prawdziwe dla wszystkich \(\displaystyle{ n<N!}\).
Dla \(\displaystyle{ N!\leq n<(N+1)!}\) istnieje dokładnie jedno \(\displaystyle{ d_N\leq N}\) takie, że \(\displaystyle{ d_NN!\leq n<(d_N+1)N!}\).
Wtedy liczba \(\displaystyle{ n-d_NN!<N!}\) ma jednoznaczny rozkład \(\displaystyle{ \sum_{i=1}^{N-1} d_ii!}\) i stąd \(\displaystyle{ n=\sum_{i=1}^{N-1} d_ii!+d_NN!}\) jest szukanym jednoznacznym rozkładem.

[patryk00714]

Wielkie dzięki!
A da się to wyprowadzić, jakoś na podstawie tego, że każdą liczbę naturalną da się przedstawić, jako \(\displaystyle{ n=p_1^{\alpha_1} \cdot p_2^{\alpha_2} ... p_k ^{\alpha_k}}\), gdzie \(\displaystyle{ p_i \in \mathbb{P}}\)

[a4karo]

chyba nie, to są dwa różne mechanizmy

[patryk00714]

Pytam, bo to zadanko mam w dziale o wlasnosciach liczb pierwszych, w ktorym jest wlasnie podane to przedstawienie.

[Ponewor]

"To" przedstawienie, to nie jest jakieś tam byle przedstawienie, tylko rozkład na czynniki pierwsze.

Możesz natomiast zasugerować się samym szkieletem dowodu - jakaś indukcja, a następnie dowód jednoznaczności.