Dimostrazione per induzione
Provare che $(x-1)^n<=x^n-1$.
Base dell'induzione:
$n=1$ $(x-1)^1<=x^1-1$ vero.
Passo induttivo:
Sia $(x-1)^n<=x^n-1$ per n fissato.
Allora $(x-1)^(n+1)<=(x^n-1)(x-1)=x^(n+1)-x^n-x+1$.
Ho provato a vedere se si poteva dimostrare che $x^(n+1)-x^n-x+1<=x^(n+1)-1$ ma questo non è vero...
In che altro modo posso procedere?
Base dell'induzione:
$n=1$ $(x-1)^1<=x^1-1$ vero.
Passo induttivo:
Sia $(x-1)^n<=x^n-1$ per n fissato.
Allora $(x-1)^(n+1)<=(x^n-1)(x-1)=x^(n+1)-x^n-x+1$.
Ho provato a vedere se si poteva dimostrare che $x^(n+1)-x^n-x+1<=x^(n+1)-1$ ma questo non è vero...
In che altro modo posso procedere?
Risposte
La disuguaglianza $(x-1)^n leq x^n -1$ è falsa: prendere $x=0, n=2$.
Ho dimenticato di specificare che $x>=1inRR$ e $n>=1inNN$
"thedarkhero":
[...]
Ho provato a vedere se si poteva dimostrare che $x^(n+1)-x^n-x+1<=x^(n+1)-1$ ma questo non è vero...
In che altro modo posso procedere?
$x^(n+1)-x^n-x+1<=x^(n+1)-1=> -x^n-x+2<=0$. Nota che per $x=1$ hai l'uguaglianza, se riesci a dimostrare che la funzione $f:[1, +oo)->RR$, definita da $f(x)= -x^n-x+2$ è decrescente rispetto ad x allora hai finito
"thedarkhero":
Ho provato a vedere se si poteva dimostrare che $x^(n+1)-x^n-x+1<=x^(n+1)-1$ ma questo non è vero...
In che altro modo posso procedere?
perchè non è vero?
$x^(n+1)-x^n-x+1<=x^(n+1)-1$ ; $x^n + x>=2$ il che è verificato per le ipotesi $x inRR$,$ x>=1$,$n in NN_0$
in quanto $x>=1$ e $x^n>=1$ e perciò la loro somma è maggiore o uguale a 2
Hai ragione, ho dimostrato che la funzione è decrescente come mi aveva suggerito Mathematico.
Ora, altro problema.
Sia $n>=1$. Sia data una scacchiera $2^n$x$2^n$. Si tolga una casella. Mostrare che si può ricoprire senza sovrapposizioni con pezzi quadrati 2x2 a cui viene tolta una casella.
Il caso base con n=1 è semplice in quanto una scacchiera $2^1$x$2^1$ a cui viene tolta una casella coincide con un pezzo quadrato 2x2 a cui viene tolta una casella.
Ma per il passo induttivo come si può mostrare che se una scacchiera $2^n$x$2^n$-1 si può ricoprire con quadrati 2x2-1 allora anche una scacchiera $2^(n+1)$x$2^(n+1)$-1 è ricopribile?
Ora, altro problema.
Sia $n>=1$. Sia data una scacchiera $2^n$x$2^n$. Si tolga una casella. Mostrare che si può ricoprire senza sovrapposizioni con pezzi quadrati 2x2 a cui viene tolta una casella.
Il caso base con n=1 è semplice in quanto una scacchiera $2^1$x$2^1$ a cui viene tolta una casella coincide con un pezzo quadrato 2x2 a cui viene tolta una casella.
Ma per il passo induttivo come si può mostrare che se una scacchiera $2^n$x$2^n$-1 si può ricoprire con quadrati 2x2-1 allora anche una scacchiera $2^(n+1)$x$2^(n+1)$-1 è ricopribile?
ho un idea che credo sia giusta, però non so se è facile da capire senza disegno, quindi vado passo passo:
abbiamo dimostrato che fino a un valore $n$ è possibile ricoprire la scacchiera di $2^n * 2^n -1$ caselle con i pezzi $2*2-1$.
consideriamo la scacchiera di $2^(n+1) * 2^(n+1)$ caselle:
è formata da quattro scacchiere di $2^n * 2^n $ caselle affiancate, capito come, no?
ebbene dalla scacchiera "grossa", quella di $2^(n+1) * 2^(n+1)$ caselle togliamo una casella a caso:
la toglieremo da una delle 4 piccole. Ebbene questa piccola da cui abbiamo tolto la casella la possiamo ricoprire con i pezzi $2*2 -1$ per ipotesi induttiva.
le altre 3 le possiamo sicuramente ricoprire con i pezzi $2*2-1$ lasciando una casella vuota, sempre per la stessa ipotesi;
inoltre possiamo lasciare una qualunque casella vuota, e decidiamo di lasciare vuote tre delle 4 caselle centrali della scacchiera "grande", ovvero le caselle negli spigoli (in alto, in basso, a destra, a sinistra, dipende) delle 3 piccole senza buchi, in modo da poter utilizzare un pezzo $2*2-1$ per ricoprire queste tre caselle vuote. Perciò la tesi è dimostrata.
abbiamo dimostrato che fino a un valore $n$ è possibile ricoprire la scacchiera di $2^n * 2^n -1$ caselle con i pezzi $2*2-1$.
consideriamo la scacchiera di $2^(n+1) * 2^(n+1)$ caselle:
è formata da quattro scacchiere di $2^n * 2^n $ caselle affiancate, capito come, no?
ebbene dalla scacchiera "grossa", quella di $2^(n+1) * 2^(n+1)$ caselle togliamo una casella a caso:
la toglieremo da una delle 4 piccole. Ebbene questa piccola da cui abbiamo tolto la casella la possiamo ricoprire con i pezzi $2*2 -1$ per ipotesi induttiva.
le altre 3 le possiamo sicuramente ricoprire con i pezzi $2*2-1$ lasciando una casella vuota, sempre per la stessa ipotesi;
inoltre possiamo lasciare una qualunque casella vuota, e decidiamo di lasciare vuote tre delle 4 caselle centrali della scacchiera "grande", ovvero le caselle negli spigoli (in alto, in basso, a destra, a sinistra, dipende) delle 3 piccole senza buchi, in modo da poter utilizzare un pezzo $2*2-1$ per ricoprire queste tre caselle vuote. Perciò la tesi è dimostrata.
ho capito, buona idea!
grazie ancora
grazie ancora
Sia $n>=1$ naturale. Mostrare che $(a+b)^n=\sum_{k=0}^n ((n),(k))a^kb^(n-k)$.
Base dell'induzione: banalmente verificata per n=1.
Per il passo induttivo si può usare la formula di Stiefel $((n),(k))=((n-1),(k))-((n-1),(k-1))$ ma non so come...
Base dell'induzione: banalmente verificata per n=1.
Per il passo induttivo si può usare la formula di Stiefel $((n),(k))=((n-1),(k))-((n-1),(k-1))$ ma non so come...
Un'altra dimostrazione interessante è $\sum_{k=0}^n ((n),(k))(-1)^k*k=0$.
Ho provato ad usare la formula di Stiefel ma non sono riuscito ad arrivare da nessuna parte.
Ho provato ad usare la formula di Stiefel ma non sono riuscito ad arrivare da nessuna parte.
"thedarkhero":
Un'altra dimostrazione interessante è $\sum_{k=0}^n ((n),(k))(-1)^k*k=0$.
Ho provato ad usare la formula di Stiefel ma non sono riuscito ad arrivare da nessuna parte.
Era un pò che non mi buttavo in una dimostrazione... provo a divertirmi io.
Per $n = 2$ la verifica è immediata. Supponiamo ora la formula valga per $n$, si ha:
$\sum_{k=0}^(n+1) ((n+1),(k))(-1)^k*k = \sum_{k=0}^(n) ((n+1),(k))(-1)^k*k + (-1)^(n+1)(n+1) = \sum_{k=0}^(n) ((n),(k))(-1)^k*k + \sum_{k=0}^(n) ((n),(k-1))(-1)^k*k + (-1)^(n+1)(n+1) =$
$= 0 + \sum_{k=1}^(n) ((n),(k-1))(-1)^k*k + (-1)^(n+1)(n+1) = \sum_{j=0}^(n-1) ((n),(j))(-1)^(j+1)*(j+1) + (-1)^(n+1)(n+1) = \sum_{j=0}^(n) ((n),(j))(-1)^(j+1)*(j+1) -(-1)^(n+1)(n+1) +(-1)^(n+1)(n+1) = $
$= -\sum_{j=0}^(n) ((n),(j))(-1)^j*j -\sum_{j=0}^(n) ((n),(j))(-1)^j + 0 = 0 + 0 = 0$.
(Il primo 0 è per ipotesi induttiva, il secondo è somma di termini uguali, il terzo sempre per ipotesi induttiva e il quarto si dimostra subito con il binomio di newton applicato a $a = 1$ e $b = -1$).
P.S. Rileggendo, mi sa l'ultimo passaggio della seconda riga potevo evitarlo...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo