Parole... palindrome

[bĕlcōlŏn]

Definisco una sequenza di parole $A$ in questo modo: $A_0=a$, $A_1=b$ e ogni parola $A_n$ con $n \geq 2$ si ottiene accostando $A_{n-2} A_{n-1}$. Dimostrare che per ogni $n\geq 1$ accostando le parole $A_1A_2...A_n$ se ne ottiene una palindroma.

[SkZ]

intendi in pratica una serie stile fibonacci? ogni parola e' la "somma' delle 2 che precedono?
a, b, ab, bab, ...

[bĕlcōlŏn]

intendi in pratica una serie stile fibonacci? ogni parola e' la "somma' delle 2 che precedono?
a, b, ab, bab, ...

Esattamente.

[balossino]

Provo a rispondere io... siate clementi se non uso il latex, è il mio primo giorno

Data una serie A(1)A(2)...A(n), definiamo una "mossa" come il passaggio alla serie successiva [cioè quella che termina con A(n+1)]. Si verifica banalmente che A(1)A(2) => bab è una serie palindroma. Cercheremo di dimostrare la proprietà richiesta per induzione. Ogni mossa può essere descritta come l'aggiunta del termine A(n+1). Esso appartiene alla coda della serie, perché è stato formato con gli ultimi due termini aggiunti nella mossa precedente. Ma allora, per simmetria (perché abbiamo detto che la serie è palindroma), possiamo considerare A(n+1) come la prima parte della serie precedente, specchiata. A questo punto, sempre per simmetria, avremo ottenuto una nuova serie palindroma.

[bĕlcōlŏn]

Esso appartiene alla coda della serie, perché è stato formato con gli ultimi due termini aggiunti nella mossa precedente. Ma allora, per simmetria (perché abbiamo detto che la serie è palindroma), possiamo considerare A(n+1) come la prima parte della serie precedente, specchiata.

Forse ho capito cosa intendi, ma non ne sono sicuro, potresti essere più chiaro?

[ileo83]

scusate ma gia' al passo 2 la parola non e' palindroma. cioe' abab, che sarebbe a+b+ab, non e' mica palindroma deh!

[Drago96]

scusate ma gia' al passo 2 la parola non e' palindroma. cioe' abab, che sarebbe a+b+ab, non e' mica palindroma deh!

$a=A_0$ Invece il problema dice "accostando le parole $A_1A_2...A_n$"

[kalu]

Per ogni intero positivo $ n $, chiamo $ K_n $ la parola ottenuta accostando $ A_1A_2...A_n $.
$ K_1=A_1=b $, ed è chiaramente pailndroma. Proverò a dimostrare che $ K_n $ è palindroma per ogni $ n>1 $.
Per ogni $ n>1 $, chiamo $ R_n $ (radice di $ A_n $) la parte iniziale di $ A_n $, costituita dalle sue prime due lettere; chiamo invece $ D_n $ (desinenza di $ A_n $) la parte finale di $ A_n $, che segue $ R_n $ (quindi $ A_n=R_nD_n $).
Dimostro per induzione che, per ogni intero positivo $ n $, $ R_{2n}=ab $ e $ R_{2n+1}=ba $. Noto che è così per $ n=1 $; supponendo che la proprietà si verificata per $ n $ osservo che $ A_{2n+2}=A_{2n}A_{2n+1} $ (e dunque $ R_{2n+2}=R_{2n} $), mentre $ A_{2n+3}=A_{2n+1}A_{2n+2} $ (e dunque $ R_{2n+3}=R_{2n+1} $).
Dimostro ora per induzione che $ D_n=K_{n-2} $ (qualora $ D_n $ esista). $ D_2 $ non esiste, mentre per $ n=3 $ e $ n=4 $ la proprietà è verificata. Suppongo che la proprietà sia verificata per $ n $ e per $ n-1 $ ($ n\ge4 $). Allora $ D_{n+1}=D_{n-1}+A_{n}=K_{n-3}A_{n-2}A_{n-1}=K_{n-1} $.
A questo punto dimostro la tesi per induzione. $ K_2 $, $ K_3 $ e $ K_4 $ sono palindrome. Suppongo che $ K_{n-1} $ e $ K_{n-2} $ siano palindrome ($ n\ge4 $). Allora $ K_{n+1}=K_{n-1}R_{n}D_{n}R_{n+1}D_{n+1}=K_{n-1}R_{n}K_{n-2}R_{n+1}K_{n-1} $. $ K_{n-1} $ e $ K_{n-2} $ sono palindrome per ipotesi induttiva, inoltre $ R_n $ e $ R_{n+1} $ sono speculari essendo rispettivamente $ ab $ e $ ba $ o viceversa: quindi $ K_{n+1} $ è palindroma.

[bĕlcōlŏn]

Perfetto kalu, è identica alla mia

[kalu]

oh bene belcolon (perdonami le quantità), per me è un onore scrivere dimostrazioni identiche alle tue