Rappresentazione tramite Fibonacci

[Gauss91]

Dimostrare che ogni numero naturale a è esprimibile IN MODO UNICO nella forma

$ a = F_{n_1} + F_{n_2} + \ldots + F_{n_m} $ dove
$ 1 \le m $, $ n_j \le n_{j-1} - 2 $ per ogni $ j = 1, 2, \ldots, m $, e $ n_m > 1 $.
e dove $ F_k $ è il k-esimo numero di Fibonacci (si intende $ F_1 = 1, F_2 = 1, F_3 = 2, \ldots $)

Il fatto che sia esprimibile non è molto problematico, l'unicità della rappresentazione invece un po' di più. Buon lavoro

[jordan]

Una generalizzazione di questo fatto era stata proposta per l'oliforum contest da Darij Gringberg, poi abbiamo optato per qualcosa di meno tecnico ^^

[dario2994]

Jordan puoi scrivere la generalizzazione che sono curioso...

[Gauss91]

Una generalizzazione di questo fatto era stata proposta per l'oliforum contest da Darij Gringberg, poi abbiamo optato per qualcosa di meno tecnico ^^

Forse ho capito male, ma questo problema non è per nulla tecnico... se sono riuscito a risolverlo io significa anzi che è molto alla portata di un risolutore di livello medio-basso come me (l'ho preso dal LeVeque).
O il "tecnico" si riferisce solo alla generalizzazione?

[dario2994]

Ti confermo che questo problema non è affatto tecnico Penso si riferisca alla generalizzazione.

[fph]

Sull'Engel il risultato è noto con il divertente nome di lemma di Zeckendorf.

[Gauss91]

[quote=fph]Sull'Engel il risultato è noto con il divertente nome di lemma di Zeckendorf.[/quote]

Ah! Non l'avevo visto! Bene non si finisce mai di imparare!

[fph]

Se non mi sbaglio è l'ultima voce dell'indice analitico. E sulla pagina di Wikipedia (inglese) di questo celebrato teorema c'è anche questo fatterello carino che vi invito a provare:

One can define the following operation $ a\circ b $ on natural numbers ''a'', ''b'': given the Zeckendorf representations
$ a=\sum_{i=0}^kF_{c_i}\;(c_i\ge2) $ and $ b=\sum_{j=0}^lF_{d_j}\;(d_j\ge2) $ we define the '''Fibonacci product''' $ a\circ b=\sum_{i=0}^k\sum_{j=0}^lF_{c_i+d_j}. $

For example, the Zeckendorf representation of 2 is F_3, and the Zeckendorf representation of 4 is F_4 + F_2 (F_1 is disallowed from representations), so $ 2 \circ 4 = F_{3+4} + F_{3+2} = 13 + 5 = 18. $

Donald Knuth proved the surprising fact that this operation is associative.

[jordan]

Sull'Engel il risultato è noto con il divertente nome di lemma di Zeckendorf.

Esattamente; il tecnico si riferiva alla generalizzazione, si.. per quest'ultima (vi prego di non divulgarla almeno per adesso):
"Sia $ t \in \mathbb{N} $ fissato e sia fissato $ T=\{a_1,a_2,\ldots,a_t\}\subseteq \mathbb{Z} $; inoltre un insieme $ S \subseteq \mathbb{Z} $ è detto buono se $ s \in S $ implica $ s+1 \not \in S $. Sapendo che vale l'identità $ \displaystyle \sum_{s \in S}{f_{n+s}}=\sum_{a_i \in T}{f_{n+a_i}} $ per ogni intero n sufficientemente grande, mostrare che un insieme S buono esiste ed è unico."

[dario2994]

Uhm... Jordan con grandi sforzi penso di essere riuscito a risolvere la generalizzazione. Non è particolarmente tecnica, l'unico fatto non elementare che ho usato è:

Definito [x] l'intero più vicino a x vale:
$ $[\phi F_n]=F_{n+1} $

Non scrivo la dimostrazione un po' perchè è lunghetta, un po perchè hai detto di non divulgare quindi presumo che la soluzione sia meglio non postarla.

[jordan]

Si, ci hai preso ^^
E ti ringrazio per non averla postata