Funzione salterello

[Oblomov]

Spostato in MNE. Problemi auto-posti o comunque non "chiaramente di tipo olimpiadi" andrebbero messi in MNE e non nelle quattro categorie olimpiche. --federico
----------------------

Ecco una stranissima funzione ricorsiva,che ho battezzato "funzione salterello".
F(0)=1
e f(N)=f(N-1)°N
Il simbolino ° é alternativamente più,meno,per,diviso.
Cioé partendo da uno si aggiunge uno,si sottrae due,si moltiplica per tre,si divide per quattro,si aggiunge cinque,si sottrae sei ecc.
A occhio direi che la funzione tende a zero.Ma il vero problema é:come si calcola f(x)?Come cambia la successione se cambio l'ordine degli operatori primari?
Saluti!
Oblomov

[Laurentius]

Nota: discorso poco rigoroso. La numerazione dei passi l'ho indicata in almeno tre modi diversi senza indicare esplicitamente il passaggio dall'uno all'altro... spero si capisca lo stesso)

La funzione va a cicli di quattro passi: nei primi due si somma N e si sottrae N+1, quindi in totale si sottrae 1; nei secondi due si moltiplica per N e si divide per N+1, quindi si diminuisce leggermente il valore assoluto. Riassumendo: (X-1)*N/(N+1).
Si vede quindi immediatamente che se ad un certo punto X diventa negativo (e succede quasi subito), lo resterà sempre.
Inoltre, ad ogni ciclo decresce, ma sempre meno di 1: è F(I)-1 < F(I+1) < F(I)
Si dimostrano separatamente le due parti.
Se x=F(I), allora F(I+1) < F(I) diventa:
(x-1)*N/{N+1} < x
x*N/{N+1} - N/{N+1} < x
x*N/{N+1} - N/{N+1} < x
-x/(N+1) < N/{N+1}
-x < N
x > -N

F(I)-1 < F(I+1) invece diventa:
x-1 < (x-1)*N/{N+1}
x-1 < (x-1)-(x-1)/{N+1}
0 < -(x-1)
0 < -x+1)
x < 1

Quindi se f(i)<1, allora f(i)-1 < f(i+1). Ma già dopo il primo passo x=0, e dopo il secondo è negativo, e abbiamo visto che resterà sempre negativo, quindi la disuguaglianza vale sempre.
Abbiamo visto poi che F(I+1) < F(I) (la funzione, di ciclo in ciclo, è strettamente decrescente) se x > -N; ma sappiamo che già dopo il primo passo (N=4, x=0) è così, e mentre N incrementa sempre di 4, x decrementa sempre di meno di uno, quindi resterà così per sempre.
Quindi... la funzione è strettamente decrescente. Però potrebbe avere un asintoto da qualche parte.
Allora proviamo a dimostrare che F(I+1) < F(I) - 1/2
Si trova che è vero per x > -n/2+1. Sappiamo che esistono degli X particolari per cui questo è valido, e per induzione si dimostra che è vero definitivamente... l'ho fatto su carta e non ho voglia di riscriverlo bene.

Cambiando l'ordine degli operatori: scambiano * e /, tende comunque a meno infinito (ma più velocemente). Scambiando + e -, tende a più infinito. Altre cose sono più complicate e non c'ho pensato...


Fra l'altro, prima che facessi i conti a mano, il mio computer mi ha gentilmente calcolato la funzione fino ad N=10^8, e conferma. (per N=
99999997, x=-19999998.9899096344)

(se a qualcuno interessasse, lo script per bc che ho usato per calcolarlo:
#!/usr/bin/bc -q

scale=10
x=1
passi=10^2
scalini=10^6

for(j=0; j<passi; j++){
max=((j+1)*scalini-10)
for(i=j*scalini+1; i<max; i+=4){
x=(x-1)*(i+2)/(i+3)
}
for(;i<max+10;i+=4){
print i, ": \t", x, "\n"
x=(x-1)*(i+2)/(i+3)
}
}

[Oblomov]

Ringrazio Laurentius per la risposta.Ma io cercavo una funzione che cosideri tutti i valori e non solo quelli alla fine di un ciclo(lì sta il difficile).
Poi ripeto la domanda:che succede se cambio l'ordine degli operatori?
Saluti,
Oblomov

[Laurentius]

Mah, non credo si possa fare molto meglio della definizione per ricorsione che hai dato. Comunque, si vede che ad ogni ciclo diminuisce di un po' meno di 1 (ad occhio, il passo tende a 1, ma non ne sono sicurissimo).