OliForum Matematico

Dimostrare che, scritti in binario, i numeri di $ N $ cifre che non contengono $ 001 $ sono esattamente l'$ (N+3) $-esimo numero della successione di Fibonacci diminuito di uno. Si consideri $ F_0 = 0; \enspace F_1 = 1; \enspace F_2 = 1; \enspace F_3 = 2, \enspace ... $ con $ F_x = $ l' $ x $-esimo numero di Fibonacci

Esempio: per $ N = 5 $ si hanno $ 2^5 = 32 $ possibilità, dalle quali bisogna eliminarne $ 12 $ ($ 00001; $ $ 00010; $ $ 00011; $ $ 00100; $ $ 00101; $ $ 00110; $ $ 00111; $ $ 01001; $ $ 10001; $ $ 10010; $ $ 10011; $ $ 11001 $) perchè contengono $ 001 $. Quindi restano $ 20 $ i numeri di $ 5 $ cifre binarie che non contengono $ 001 $.
$ F_{5+3}=F_8=21 $, si può notare immediatamente che $ 20 $ è $ 21 $ diminuito di uno.

Sia $X_n$ il numero di modi di scrivere una stringa di $n$ cifre seguendo le regole. Proviamo ad impostare una relazione di ricorrenza dividendo in casi:
Caso 1): Se la stringa comincia per $1$, abbiamo $X_{n-1}$ modi di completarla, poiché questa cifra non ci pone ulteriori limitazioni sulle successive $n-1$.
Caso 2): Se la stringa comincia per $0$, abbiamo due sottocasi:
Sottocaso 2a): Se la stringa comincia per $01$, abbiamo $X_{n-2}$ modi di completarla, poiché questa sequenza di cifre non ci pone ulteriori limitazioni sulle successive $n-2$.
Sottocaso 2b): Se la stringa comincia per $00$, tutte le cifre seguenti dovranno essere per forza zeri, altrimenti si verrebbe a formare la sottostringa $001$, quindi c'è un solo modo di completarla.

Ma così abbiamo considerato tutte le possibilità, e dunque sommando questi casi (sono infatti tutti disgiunti), otteniamo proprio il numero di modi di formare una stringa di $n$ cifre seguendo le limitazioni del problema, ovvero:
$$X_n=X_{n-1}+X_{n-2}+1$$
Si verifica facilmente a mano che $X_1=2^1=2=F_{1+3}-1$ e $X_2=2^2=4=F_{2+3}-1$ e quindi per questi due numeri la tesi è valida, dimostriamola dunque per induzione su $n$ (assumendola vera per $n$ e $n+1$, la dimostriamo per $n+2$), sfruttando la relazione appena trovata:
$$X_{n+2}=X_{n+1}+X_{n}+1\ \ \ \Rightarrow\ \ \ X_{n+2}=(F_{n+4}-1)+(F_{n+3}-1)+1=F_{n+5}-1$$
E abbiamo finito.