\(\displaystyle a_0=1 \)
\(\displaystyle a_{n+1}=\begin{cases} \frac{a_n}{2}, & \mbox{se }a_n\mbox{ pari} \\ a_n+h, & \mbox{se }a_n\mbox{ dispari}
\end{cases} \)
Per quali valori di \(\displaystyle h \) esiste \(\displaystyle n>0 \) tale che \(\displaystyle a_n=1 \)?
Qui metto la mia soluzione, che usa l'induzione, su cui ho un forte dubbio:
Testo nascosto, fai click qui per vederlo
Chiaramente se \(\displaystyle h \) è pari allora \(\displaystyle n \) non esiste, poiché avrei \(\displaystyle a_n=1+hn \) \(\displaystyle \forall n >0\)
Viceversa \(\displaystyle n \) esiste sempre purchè \(\displaystyle h \) sia dispari. Ora uso il principio di induzione forte su \(\displaystyle k \), imponendo \(\displaystyle h=2k-1 \). Vale chiaramente per \(\displaystyle k=1 \), ma è facile anche il caso di \(\displaystyle k=3 \). Lo suppongo vero fino ad un certo naturale \(\displaystyle k-1 \) da cui \(\displaystyle h=2k-1 \) e dimostro che è vero per \(\displaystyle k+1 \) ossia \(\displaystyle h=2k+1 \). Avrò infatti \(\displaystyle a_1=2k+2 \). Per cui avrò \(\displaystyle a_2=k+1<2k-1 \), adesso se \(\displaystyle k+1 \) è una potenza del 2 arriverò direttamente usando solo la prima trasformazione al termine 1, se invece \(\displaystyle k+1 \) ha qualche fattore dispari, arriverò ugualmente ad ottenere 1 perché dopo aver tolto tutti i fattori 2 otterrò sicuramente un numero dispari inferiori a \(\displaystyle 2k+1 \), e per ipotesi induttiva tutti i dispari inferiori a \(\displaystyle 2k+1 \) arrivavano ad 1. La dimostrazione sarebbe completa ma questa parte con l'induzione non mi convince. C'è qualche errore nell'uso del principio d'induzione o va bene così?
Viceversa \(\displaystyle n \) esiste sempre purchè \(\displaystyle h \) sia dispari. Ora uso il principio di induzione forte su \(\displaystyle k \), imponendo \(\displaystyle h=2k-1 \). Vale chiaramente per \(\displaystyle k=1 \), ma è facile anche il caso di \(\displaystyle k=3 \). Lo suppongo vero fino ad un certo naturale \(\displaystyle k-1 \) da cui \(\displaystyle h=2k-1 \) e dimostro che è vero per \(\displaystyle k+1 \) ossia \(\displaystyle h=2k+1 \). Avrò infatti \(\displaystyle a_1=2k+2 \). Per cui avrò \(\displaystyle a_2=k+1<2k-1 \), adesso se \(\displaystyle k+1 \) è una potenza del 2 arriverò direttamente usando solo la prima trasformazione al termine 1, se invece \(\displaystyle k+1 \) ha qualche fattore dispari, arriverò ugualmente ad ottenere 1 perché dopo aver tolto tutti i fattori 2 otterrò sicuramente un numero dispari inferiori a \(\displaystyle 2k+1 \), e per ipotesi induttiva tutti i dispari inferiori a \(\displaystyle 2k+1 \) arrivavano ad 1. La dimostrazione sarebbe completa ma questa parte con l'induzione non mi convince. C'è qualche errore nell'uso del principio d'induzione o va bene così?
