Discussione:
Applicazione principio di induzione
Aggiungi Risposta
Gianluca
2018-11-26 09:37:17 UTC
Rispondi
Permalink
Ho incontrato un esercizio che dovrebbe essere banale, ma non riesco a
trovare la strada giusta per affrontarlo.

Si parla di successioni.

Trovare il più grande tra:
- n^(n+1)
- (n+1)^n

Posso dire che:
n^(n+1)<(n+1)^(n+1)

e anche che:
(n+1)^n<(n+1)^(n+1)

ma non so come legare i due primi termini.
Deve essere qualcosa di banale ma non riesco a vederlo...


Gianluca
effe
2018-11-26 12:37:35 UTC
Rispondi
Permalink
Post by Gianluca
- n^(n+1)
- (n+1)^n
n^(n+1)<(n+1)^(n+1)
(n+1)^n<(n+1)^(n+1)
ma non so come legare i due primi termini.
Deve essere qualcosa di banale ma non riesco a vederlo...
Io la vedo così.
Se n=1 abbiamo che 1^2<2^1 quindi è vero.

Ammettiamo vero che n^(n+1) < (n+1)^n
abbiamo per il primo membro n^(n+1)(n+1)<(n+1)^(n+1)(n+1)=(n+1)^(n+2)
<
secondo membro (n+1)^n(n+1)=(n+1)^(n+1) che è < (n+2)^(n+1)
cioè (n+1)^(n+2)<(n+2)^(n+1)
Quindi è vero per ogni n.
El Filibustero
2018-11-26 13:23:49 UTC
Rispondi
Permalink
Post by effe
cioè (n+1)^(n+2)<(n+2)^(n+1)
Quindi è vero per ogni n
vero per ogni n<2. per n>=3 e' vero il contrario. Ciao
effe
2018-11-26 13:35:46 UTC
Rispondi
Permalink
Post by El Filibustero
Post by effe
cioè (n+1)^(n+2)<(n+2)^(n+1)
Quindi è vero per ogni n
vero per ogni n<2. per n>=3 e' vero il contrario. Ciao
Cazzarola! Hai ragione!
El Filibustero
2018-11-26 13:22:18 UTC
Rispondi
Permalink
Post by Gianluca
Ho incontrato un esercizio che dovrebbe essere banale, ma non riesco a
trovare la strada giusta per affrontarlo.
Si parla di successioni.
- n^(n+1)
- (n+1)^n
Deve essere qualcosa di banale ma non riesco a vederlo...
si ha (n+1)^n < n^(n+1) da n=3 in su.

Per ogni numero naturale,

(n+2)/(n+1)<(n+1)/n, quindi [(n+2)/(n+1)]^(n+1) < [(n+1)/n]^(n+1) (*)

Ammettiamo che esista (ed esiste, e' 3, ad esempio) un n per cui

(n+1)^n < n^(n+1)

ossia [(n+1)/n]^n < n, sicche' [(n+1)/n]^(n+1) < n[(n+1)/n] = n+1.

Hint: mettere assieme [(n+1)/n]^(n+1) < n+1 e (*). Ciao
Gianluca
2018-11-26 17:48:39 UTC
Rispondi
Permalink
Il 26/11/18 14:22, El Filibustero ha scritto:> si ha (n+1)^n < n^(n+1)
da n=3 in su.
Post by El Filibustero
Per ogni numero naturale,
(n+2)/(n+1)<(n+1)/n, quindi [(n+2)/(n+1)]^(n+1) < [(n+1)/n]^(n+1) (*)
Ammettiamo che esista (ed esiste, e' 3, ad esempio) un n per cui
(n+1)^n < n^(n+1)
ossia [(n+1)/n]^n < n, sicche' [(n+1)/n]^(n+1) < n[(n+1)/n] = n+1.
Hint: mettere assieme [(n+1)/n]^(n+1) < n+1 e (*). Ciao
Per n>=3,
(n+1)^n < n^(n+1)
Dividendo per n^n entrambi i membri si ha
(1 + 1/n)^n < n
Ora,
(1 + 1/(n+1))^(n+1) < (1 + 1/n)^(n+1) = ... < ...
Kiuhnm
Grazie ad entrambi.
Provo a vedere se riesco a chiedere il cerchio.
Oggi, causa impegni di lavoro, ho solo abbozzato i primi passaggi.

Gianluca
socratis
2018-11-26 18:29:28 UTC
Rispondi
Permalink
Post by Gianluca
Il 26/11/18 14:22, El Filibustero ha scritto:> si ha (n+1)^n < n^(n+1)
da n=3 in su.
Post by El Filibustero
Per ogni numero naturale,
(n+2)/(n+1)<(n+1)/n, quindi [(n+2)/(n+1)]^(n+1) < [(n+1)/n]^(n+1) (*)
Ammettiamo che esista (ed esiste, e' 3, ad esempio) un n per cui
(n+1)^n < n^(n+1)
ossia [(n+1)/n]^n < n, sicche' [(n+1)/n]^(n+1) < n[(n+1)/n] = n+1.
Hint: mettere assieme [(n+1)/n]^(n+1) < n+1 e (*). Ciao
Per n>=3,
(n+1)^n < n^(n+1)
Dividendo per n^n entrambi i membri si ha
(1 + 1/n)^n < n
Ora,
(1 + 1/(n+1))^(n+1) < (1 + 1/n)^(n+1) = ... < ...
Kiuhnm
Grazie ad entrambi.
Provo a vedere se riesco a chiedere il cerchio.
Oggi, causa impegni di lavoro, ho solo abbozzato i primi passaggi.
Ti/Vi, ricordo che qualsiasi unità Vale 10 decimali,+
che 1 = 10dm, e che 10dm)^2 = 100dm = 10 (1)
Il decimale di 1 è il dm ed è stato battezzato col nome di i .

Socratis
Gianluca
2018-12-02 19:37:35 UTC
Rispondi
Permalink
Post by El Filibustero
Per ogni numero naturale,
(n+2)/(n+1)<(n+1)/n, quindi [(n+2)/(n+1)]^(n+1) < [(n+1)/n]^(n+1) (*)
Ammettiamo che esista (ed esiste, e' 3, ad esempio) un n per cui
(n+1)^n < n^(n+1)
ossia [(n+1)/n]^n < n, sicche' [(n+1)/n]^(n+1) < n[(n+1)/n] = n+1.
Hint: mettere assieme [(n+1)/n]^(n+1) < n+1 e (*). Ciao
Ho provato ma non ci riesco.

1) [(n+2)/(n+1)]^(n+1) < [(n+1)/n]^(n+1)

2) (n+1)^n < n^(n+1) --> [(n+1)/n]^n < n

[(n+1)/n]^n < n la scrivo come suggerito da Kiuhnm:
[1+1/n]^n < n

da cui [1+1/n]^n > [1+1/(n+1)]^n

se al posto di n elevo alla (n+1) è ancora valida:

[1+1/n]^(n+1) > [1+1/(n+1)]^(n+1), cioè:

[(n+1)/n]^(n+1) > [(n+2)/(n+1)]^(n+1) che scritta con la disuguaglianza
al contrario corrisponde alla 1) per cui si può affermare che la
(n+1)^n < n^(n+1) è verificata.

Non sono convinto e non capisco dove è stato applicato il principio di
induzione...



Gianluca
ngs
2018-12-02 20:36:02 UTC
Rispondi
Permalink
Post by Gianluca
[1+1/n]^n < n
Riscrivo e completo la dim. del mio post precedente.

Vogliamo dimostrare, per induzione, che, per n >= 3,
(n+1)^n < n^(n+1) (1)

1) Passo base. Verifichiamo che la (1) vale per n=3:
(3+1)^3 = 64 < 81 = 3^(3+1)

Dividendo entrambi i membri della (1) per n^n (sempre positivo) troviamo
la disuguaglianza
(1 + 1/n)^n < n (1b)
che è equivalente alla (1), ma più facile da gestire.

Visto che la (1) e la (1b) sono equivalenti, cioè
(1) <=> (1b),
farò riferimento alla sola (1b).

2) Passo induttivo. Assumiamo che la (1b) sia vera per n = k, cioè che
(1 + 1/k)^k < k.
Vogliamo dimostrare che allora la (1b) è vera anche per n = k+1, cioè che
(1 + 1/(k+1))^(k+1) < k + 1. (2)
Dimostriamo la (2):
(1 + 1/(k+1))^(k+1) < (1 + 1/k)^(k+1)
= (1 + 1/k)^k (1 + 1/k)
< k (1 + 1/k) = k + 1,
dove l'ultimo '<' segue dall'ipotesi induttiva.

Ho introdotto la lettera k per cercare di confondere meno le idee. Di
solito si usa direttamente la n.

Kiuhnm
El Filibustero
2018-12-02 20:36:08 UTC
Rispondi
Permalink
Post by Gianluca
Post by El Filibustero
[(n+2)/(n+1)]^(n+1) < [(n+1)/n]^(n+1) (*)
Hint: mettere assieme [(n+1)/n]^(n+1) < n+1 e (*). Ciao
Ho provato ma non ci riesco.
Non sono convinto e non capisco dove è stato applicato il principio di
induzione...
La proposizione che si intende dimostrare definitivamente valida e'

p(n) := (n+1)^n < n^(n+1)

La dimostrazione per induzione consiste in:

1) trovare una base induttiva, ossia un naturale n per cui p(n) e'
vera. Questo e' facile, perche' p(3) e' vera, dato che 4^3 < 3^4.

2) provare che p(n) implica p(n+1), o -- in altri termini -- che
assumendo l'ipotesi p(n) valida, si riesce a provare la validita' di
p(n+1). In cosa consiste p(n+1)?

p(n+1) := (n+2)^(n+1) < (n+1)^(n+2)

Nel post precedente, si e' visto che assumendo p(n) vera, ne
seguirebbe che, moltiplicandone entrambi i membri per (n+1)/n^(n+1),
pure [(n+1)/n]^(n+1) < n+1 risulterebbe vera. Se mettiamo questa
relazione assieme a (*), che e' incondizionatamente valida, per la
transitivita' di < otteniamo

[(n+2)/(n+1)]^(n+1) < n+1

a condizione che valga p(n). Hint: moltiplicarne entrambi i membri per
(n+1)^(n+1). Ciao
Gianluca
2018-12-03 15:25:48 UTC
Rispondi
Permalink
Post by El Filibustero
La proposizione che si intende dimostrare definitivamente valida e'
p(n) := (n+1)^n < n^(n+1)
1) trovare una base induttiva, ossia un naturale n per cui p(n) e'
vera. Questo e' facile, perche' p(3) e' vera, dato che 4^3 < 3^4.
2) provare che p(n) implica p(n+1), o -- in altri termini -- che
assumendo l'ipotesi p(n) valida, si riesce a provare la validita' di
p(n+1). In cosa consiste p(n+1)?
p(n+1) := (n+2)^(n+1) < (n+1)^(n+2)
Nel post precedente, si e' visto che assumendo p(n) vera, ne
seguirebbe che, moltiplicandone entrambi i membri per (n+1)/n^(n+1),
pure [(n+1)/n]^(n+1) < n+1 risulterebbe vera. Se mettiamo questa
relazione assieme a (*), che e' incondizionatamente valida, per la
transitivita' di < otteniamo
[(n+2)/(n+1)]^(n+1) < n+1
Chiarissimo, ma ti chiedo ancora: sarebbe stato possibile dimostrarla
senza usare la relazione (*)? (vedi anche risposta a Kiuhnm qui sotto).
Post by El Filibustero
(1 + 1/(k+1))^(k+1) < k + 1. (2)
(1 + 1/(k+1))^(k+1) < (1 + 1/k)^(k+1)
Con questa esposizione mi riesce più facile accettare che
(1 + 1/(k+1))^(k+1) < (1 + 1/k)^(k+1) perché risulta evidente che
1/(k+1) < 1/k (k appartenente a N)

Ma questo passaggio corrisponde alla (*) che El Filibustero ha assunto
come base della sua dimostrazione.
Infatti:
(1 + 1/(k+1))^(k+1) < (1 + 1/k)^(k+1)
[(k+2)/(k+1))]^(k+1) < (k+1)^(k+1)
[(k+2)/(k+1))] < (k+1)
con k al posto di n

Quindi implicitamente usi ancora il principio di induzione, corretto?
Post by El Filibustero
= (1 + 1/k)^k (1 + 1/k)
< k (1 + 1/k) = k + 1,
dove l'ultimo '<' segue dall'ipotesi induttiva.
Ho introdotto la lettera k per cercare di confondere meno le idee. Di
solito si usa direttamente la n.
Kiuhnm
Chiarissimo, grazie.


Gianluca
ngs
2018-12-03 16:16:01 UTC
Rispondi
Permalink
Post by Gianluca
    (1 + 1/(k+1))^(k+1) < k + 1.               (2)
    (1 + 1/(k+1))^(k+1) < (1 + 1/k)^(k+1)
Con questa esposizione mi riesce più facile accettare che
 (1 + 1/(k+1))^(k+1) < (1 + 1/k)^(k+1) perché risulta evidente che
1/(k+1) < 1/k  (k appartenente a N)
Ma questo passaggio corrisponde alla (*) che El Filibustero ha assunto
come base della sua dimostrazione.
(1 + 1/(k+1))^(k+1) < (1 + 1/k)^(k+1)
[(k+2)/(k+1))]^(k+1) < (k+1)^(k+1)
[(k+2)/(k+1))] < (k+1)
con k al posto di n
Quindi implicitamente usi ancora il principio di induzione, corretto?
Uso l'induzione solo ed esclusivamente dove l'ho indicato. Il resto sono
semplici passaggi algebrici.

Preferirei che mi rispondessi separatamente, altrimenti potrebbe
sfuggirmi qualche tuo post.

Kiuhnm
Gianluca
2018-12-04 18:06:30 UTC
Rispondi
Permalink
Il 03/12/18 17:16, ngs ha scritto:> Uso l'induzione solo ed
esclusivamente dove l'ho indicato. Il resto sono
Post by ngs
semplici passaggi algebrici.
Preferirei che mi rispondessi separatamente, altrimenti potrebbe
sfuggirmi qualche tuo post.
Kiuhnm
Scusa se rispondo solo ora, ma sono parecchio impegnato col lavoro.
Cerco di spiegare le richieste di chiarimenti nell'ultimo mio post.

Posto che ho capito la dimostrazione tua e di El Filibustero mi sono
chiesto come mai mi fosse più semplice seguire il tuo ragionamento
anziché il suo.

El Filibustero partiva dalla osservazione che:
(n+2)/(n+1)<(n+1)/n
Questo mi ha lasciato perplesso, per questo gli ho chiesto se si potesse
fare a meno di questa assunzione...

Poi mi sono studiato la tua soluzione e mi sono accorto che il passaggio:
(1 + 1/(k+1))^(k+1) < (1 + 1/k)^(k+1)
(che mi risulta più /naturale/ accettare) in realtà è la stessa
(n+2)/(n+1)<(n+1)/n ma scritta in modo diverso.

Il passaggio da (1 + 1/k)
a (1 + 1/(k+1))
mi ha fatto pensare ad una applicazione /implicita/ del principio di
induzione (El Filibustero la chiama relazione "ausiliaria") mentre tu
sostieni che siano semplici passaggi algebrici.

Analisi 1 l'ho data negli anni '80 e sul mio libro di allora il
principio di induzione è trattato in mezza pagina e solo per dimostrare
la disuguaglianza di Bernoulli.
Ho trovato quell'esercizio in un altro testo che sto leggendo un po'
alla volta e anche lì l'induzione è affrontata pressoché allo stesso modo.


Gianluca
ngs
2018-12-04 18:29:07 UTC
Rispondi
Permalink
Post by Gianluca
Il 03/12/18 17:16, ngs ha scritto:> Uso l'induzione solo ed
esclusivamente dove l'ho indicato. Il resto sono
Post by ngs
semplici passaggi algebrici.
Preferirei che mi rispondessi separatamente, altrimenti potrebbe
sfuggirmi qualche tuo post.
Kiuhnm
Scusa se rispondo solo ora, ma sono parecchio impegnato col lavoro.
Cerco di spiegare le richieste di chiarimenti nell'ultimo mio post.
Posto che ho capito la dimostrazione tua e di El Filibustero mi sono
chiesto come mai mi fosse più semplice seguire il tuo ragionamento
anziché il suo.
(n+2)/(n+1)<(n+1)/n
Questo mi ha lasciato perplesso, per questo gli ho chiesto se si potesse
fare a meno di questa assunzione...
(1 + 1/(k+1))^(k+1) < (1 + 1/k)^(k+1)
(che mi risulta più /naturale/ accettare) in realtà è la stessa
(n+2)/(n+1)<(n+1)/n  ma scritta in modo diverso.
Il passaggio da (1 + 1/k)
a (1 + 1/(k+1))
mi ha fatto pensare ad una applicazione /implicita/ del principio di
induzione (El Filibustero la chiama relazione "ausiliaria") mentre tu
sostieni che siano semplici passaggi algebrici.
Analisi 1 l'ho data negli anni '80 e sul mio libro di allora il
principio di induzione è trattato in mezza pagina e solo per dimostrare
la disuguaglianza di Bernoulli.
Ho trovato quell'esercizio in un altro testo che sto leggendo un po'
alla volta e anche lì l'induzione è affrontata pressoché allo stesso modo.
E' chiaro che 1/(k+1) < 1/k potrebbe, in principio, essere anch'esso
dimostrato per induzione, ma moltiplicando entrambi i membri per k(k+1)
si trova k < k+1, che mi sembra evidentemente vera.

Allo stesso modo, (n+2)/(n+1) < (n+1)/n, moltiplicando per n(n+1)
entrambi i membri, diventa
(n+2)n < (n+1)^2 <=>
n^2 + 2n < n^2 + 2n + 1
che è evidentemente vera.

Diciamo che la mia è più semplice.

Kiuhnm

El Filibustero
2018-12-03 16:58:27 UTC
Rispondi
Permalink
Post by Gianluca
Chiarissimo, ma ti chiedo ancora: sarebbe stato possibile dimostrarla
senza usare la relazione (*)?
Si'.
Post by Gianluca
Quindi implicitamente usi ancora il principio di induzione, corretto?
Si'. ngs usa come ipotesi induttiva

p(k):= (1 + 1/k)^k < k

e come relazione "ausiliaria"

1/(k+1) < 1/k

Infatti il seguente passaggio per arrivare a p(k+1):

(1 + 1/k)^k (1 + 1/k) < k (1 + 1/k)

e' valido sse si assume la validita' di p(k) (non e' altro che e' la
disuguaglianza p(k) con entrambi i membri moltiplicati per 1 + 1/k).
Ciao
ngs
2018-11-26 13:41:05 UTC
Rispondi
Permalink
Post by Gianluca
Ho incontrato un esercizio che dovrebbe essere banale, ma non riesco a
trovare la strada giusta per affrontarlo.
Si parla di successioni.
- n^(n+1)
- (n+1)^n
n^(n+1)<(n+1)^(n+1)
(n+1)^n<(n+1)^(n+1)
ma non so come legare i due primi termini.
Deve essere qualcosa di banale ma non riesco a vederlo...
Per n>=3,
(n+1)^n < n^(n+1)
Dividendo per n^n entrambi i membri si ha
(1 + 1/n)^n < n
Ora,
(1 + 1/(n+1))^(n+1) < (1 + 1/n)^(n+1) = ... < ...

Kiuhnm
Loading...