Dimostrazione per induzione

[pcnf16]

Salve a tutti, ho questo esercizio da risolvere sfruttando il principio di induzione ma da un certo punto in poi non riesco a proseguire nella dimostrazione. Riporto la traccia dell'esercizio cosi come mi è stata assegnata.

Sia $ (a_n)_(nin N) $ una successione in N e $ b> 1 $
Se $ AA nin N $ è $ a_n < b rArr AA nin N \sum_{i=0}^n a_ib^i <b^(n+1) $

Ho proceduto in questo modo.

PASSO BASE
Per n=0 $ a_0 < b $ da cui segue banalmente la tesi.

PASSO INDUTTIVO
Suppongo vero per n che $ AA nin N $ è $ a_n < b rArr AA nin N \sum_{i=0}^n a_ib^i <b^(n+1) $. Devo dimostrare che questo è vero anche per n+1.

I miei problemi sorgono proprio in questo punto. A partire da $ a_(n+1)<b $, come faccio a sfruttare l'ipotesi induttiva e dimostrare che la disuguaglianza è vera anche per n+1? In modo particolare mi risulta impossibile riscrivere il termine n+1-esimo in modo da ricondurmi più facilmente all'ipotesi induttiva ma presumo che non sia necessario per questo esercizio.

Grazie a tutti coloro che vorranno chiarirmi questi dubbi e/o darmi qualche suggerimento per procedere nella dimostrazione.

[marco2132k]

Ciao! Scusa la risposta frettolosa (spero giusta, ma controllala!)...
Nelle tue ipotesi (\(a_n<b\) per ogni naturale \(n\)), è \(\sum_{i=0}^{n+1}a_ib^i<(1+a_{n+1})b^{n+1}\); nota che \(b\geq a_{n+1}+1\).

EDIT: corretto l'errore sul pedice.

[pcnf16]

Ciao, grazie per la risposta. Effettivamente non avevo considerato la possibilità di sfruttare l'informazione che $ a_(n+1)+1<= b $. L'unico errore da te commesso nel riscrivere la sommatoria sta solamente nel fatto che per b la i non è pedice ma apice. Tuttavia, spero mi perdonerai, non ho ben capito il passaggio logico. Facendo un passo indietro, non dovrei dimostrare prima la validità della disuguaglianza $ a_(n+1)< b $ per poi passare all'altra parte dell' implicazione riscritta per n+1 (ovvero il passaggio da te riportato)? Se non ho frainteso, sei passato direttamente a verificare che per n+1 sia vera la solo la seconda parte della implicazione ma correggimi se sbaglio. Purtroppo sono ancora alle prime armi con l'induzione, soprattutto applicata a roba più raffinata come questa rispetto ai tradizionali esercizi "didattici". Se potresti essere più chiaro/dettagliato te ne sarei infinitamente grato.

[otta96]

Ma $b$ com'è?

[pcnf16]

Ma $b$ com'è?

Cosa intendi esattamente? Ti rispondo per come ho inteso la tua domanda: b è un naturale maggiore di 1 (come ho scritto nella traccia dell’esercizio nel primo post).

[marco2132k]

Da quello che ho intuito, devi dimostrare che, data la successione \((a_n)_{n\in\mathbb{N}}\subset\mathbb{N}\) limitata superiormente da \(b\in\mathbb{N}\) (??), è \(\sum_{i=0}^{n}a_ib^i < b^{n+1}\) per ogni naturale \(n\); correggimi se ho frainteso, vd. sotto. Allora è \(a_{\nu+1}<b\) anche per il \(\nu\in\mathbb{N}\) dell'ipotesi induttiva perché se \(\nu\in\mathbb{N}\) allora \(\nu+1\in\mathbb{N}\).

Adesso che riguardo il primo post, penso che forse ti sia stato chiesto di dimostrare che "data la successione \((a_n)\) non necessariamente limitata da \(b\in\mathbb{N}\), se per ogni \(\nu\in\{0,\dots,n\}\subset\mathbb{N}\), \(a_\nu < b\) allora \(\sum_{i=0}^{n}\text{bla bla bla}\)". In questo caso, per dimostrare la "seconda implicazione" (cioè, per provare che se \(\nu\in\{1,\dots,n,n+1\}\) allora \(\sum_{i=0}^{n+1}a_ib^i < b^{n+2}\), assunta quella che è l'ipotesi induttiva) assumi che per \(\mathbb{N}\ni\nu\leq n+1\) sia \(a_\nu < b\) (\(\mathcal{P}\implies{Q}\) è vera sse, quando è vera \(\mathcal{P}\), \(\mathcal{Q}\) lo è); è ancora \(a_{n+1}+1 \leq b\) (\(n+1\in\{1,\dots,n,n+1\}\)!).

Ma $ b $ com'è?

Però in effetti se \(b\) non è un naturale nessuno ci assicura che \(a_n+1\leq b\)...

[otta96]

Cosa intendi esattamente? Ti rispondo per come ho inteso la tua domanda: b è un naturale maggiore di 1 (come ho scritto nella traccia dell’esercizio nel primo post).

Quello che non mi era chiaro era che $b$ fosse un naturale, avevo il dubbio che fosse una reale $>1$.
Se le cose stanno così allora puoi fare in questo modo: sai che $\sum_{i=0}^na_ib^i<b^(n+1)$ per ipotesi induttiva e $a_(n+1)<b^$, che implica $a_(n+1)<=b-1$, quindi $a_(n+1)b^(n+1)<=(b-1)b^(n+1)=b^(n+2)-b^(n+1)$, da cui $\sum_{i=0}^(n+1)a_ib^i=\sum_{i=0}^na_ib^i+a_(n+1)b^(n+1)<b^(n+1)+a_(n+1)b^(n+1)<=b^(n+1)+b^(n+2)-b^(n+1)=b^(n+2)$.
Questo è il metodo calcoloso di farlo, in alternativa, se hai capito veramente l'esercizio, puoi semplicemente dire che il primo membro è un numero che scritto in base $b$ ha al più $n+1$ cifre, il secondo è un numero che in base $b$ ha bisogno di $n+2$ cifre per essere scritto.
N.B. Un'ultima cosa: non ho letto le risposte di marco2132k (mi stava fatica ), è possibilissimo che le sue risposte siano anche migliori della mia, insomma leggi la mia e poi decidi con quale ti trovi meglio.

[sibelius]

non mi e' chiara una cosa, ossia quando dici che supponendo il passo induttivo vero, poi dici che devi dimostrare che questo e' vero anche per n+1.
ma il principio di induzione mi pare che non dica che tu devi dimostrare la pn+1, nel tuo caso la an+1 ma solo che la pn+1 puo' essere dedotta dalla pn

[otta96]

Dire che assumendo $P(n)$ dimostro $P(n+1)$ e da $P(n)$ si può dedurre $P(n+1)$ sono la stessa cosa.