Esercizi sul principio di induzione
Innanzitutto buona serata a tutti.
Ho provato a risolvere i seguente esercizi sul principio di induzione riguardo il quale riservo ancora qualche dubbio in fase di dimostrazione...
1)Provare che [tex]\forall n \geq 1[/tex], [tex]5 \mid {2}^{4n}-1[/tex].
2) Provare che [tex]\forall n \geq 4[/tex], [tex]n! > 2^{n}[/tex].
3) Provare che [tex]\forall n \geq 1[/tex], [tex]3 \mid {(n-1)}^3+n^{3}+{(n+1)}^3[/tex].
4) Provare che l'insieme delle parti [tex]|{\boldsymbol{P(X)}}|[/tex] di un insieme finito [tex]X[/tex] di cardinalità [tex]n[/tex](con [tex]n \geq 1[/tex]) ha [tex]2^{n}[/tex] elementi.
1)
Devo dimostrare che [tex]\forall n \geq 1[/tex][tex]\exists q : {2}^{4n}-1=5q[/tex], [tex]n,q \in \mathbb{N}[/tex]
Base dell'induzione:
[tex]P(1):= 2^{4}-1=5q \Leftrightarrow 16-1=5q \Leftrightarrow 15=5q[/tex]
Ipotesi induttiva:
[tex]P(k):= \forall k \geq 1[/tex][tex]\exists h : 2^{4k}-1=5h[/tex]
Ora supposto vera [tex]\forall k P(k)[/tex] dimostro che [tex]P(K) \Rightarrow P(k+1)[/tex]
[tex]2^{4(k+1)}-1 5q[/tex]
[tex]2^{4k}2^{4}-1=5q[/tex]
dalla [tex]P(k)[/tex] ottengo che [tex]2^{4k}=5h+1[/tex] e quindi
[tex](5h+1)2^{4}-1=5q[/tex]
[tex]5[/tex] [tex]2^{4}h+15=5q[/tex]
[tex]5(2^{4}h+3)=5q[/tex]
concludo quindi che avendo dimostrato [tex]P(k+1)[/tex] allora [tex]\forall n P(n)[/tex].
2)
Devo dimostrare che [tex]\forall n \geq 4[/tex], [tex]n! > 2^{n}[/tex].
Base dell'induzione:
[tex]P(4) := 4! > 2^{4} \Leftrightarrow 24 > 16[/tex] vera
Ipotesi induttiva:
[tex]P(k) : = k!>2^{k}[/tex]
Ora supposto vera [tex]\forall k P(k)[/tex] dimostro che [tex]P(K) \Rightarrow P(k+1)[/tex]
[tex]P(k+1):= (k+1)!>2^{(k+1)}[/tex]
moltiplicando la [tex]P(k)[/tex] a destra e a sinistra per [tex](n+1)[/tex] ottengo che
[tex](k+1)k!>2^{k}(k+1)[/tex]
considerando il membro destro della soprastante ed il membro destro della [tex]P(k+1)[/tex] ottengo che
[tex]2^{k}(k+1)>2^{k+1}[/tex]
[tex]k+1>2[/tex]
[tex]k>1[/tex] [tex]\forall k[/tex] essendo per definizione [tex]k\geq4[/tex]
quindi [tex](k+1)!>2^{k}(k+1)>2^{k+1} \Rightarrow (k+1)!>2^{k+1}[/tex] e quindi vera [tex]P(k+1)[/tex] e dimostrata [tex]\forall n P(n)[/tex].
3)
Devo dimostrare che [tex]\forall n \geq 1[/tex][tex]\exists q: (n-1)^3+n^3+(n+1)^3=3q[/tex]
Base dell'induzione:
[tex]P(1):= (1-1)^3+1^3+(1+1)^3=3q \Leftrightarrow 1+8=3q \Leftrightarrow 9=3q[/tex] vera
Ipotesi induttiva:
[tex]P(k):= \forall k \geq 1[/tex][tex]\exists h : (k-1)^3+k^3+(k+1)^3=3h[/tex]
Ora supposto vera [tex]\forall k P(k)[/tex] dimostro che [tex]P(K) \Rightarrow P(k+1)[/tex]
[tex]((k+1)-1)^3+(k+1)^3+((k+1)+1)^3=3q[/tex]
[tex]k^3+(k+1)^3+(k+2)^3=3q[/tex]
riprendendo la [tex]P(k)[/tex] ottengo che [tex]k^3+(k+1)^3=3h-(k+1)^3[/tex]
quindi ponendo quanto ottenuto nella [tex]P(k+1)[/tex] ottengo
[tex]3h-(k-1)^3+(k+2)^3=3q[/tex]
[tex]3h-(k^3-1-3k^2+3k)+(k^3+8+6k^2+12k)=3q[/tex]
[tex]3h-k^3+1+3k^2-3k+k^3+8+6k^2+12k=3q[/tex]
[tex]3h+9k^2+9k+9=3q[/tex]
[tex]3(h+3k^2+3k+3)=3q[/tex]
quindi ho dimostrato che [tex]\forall k P(k) \Rightarrow P(k+1)[/tex] e quindi che [tex]\forall n P(n)[/tex].
4)
Per tale quesito devo dimostrare che [tex]\forall n \geq 1[/tex] se [tex]|{X}|=n[/tex] allora [tex]|{\boldsymbol{P(X)}}|=2^{n}[/tex]
Base dell'induzione:
[tex]P(1):= {X}_{0} \neq \emptyset[/tex], [tex]|{{X}_{0}}|=1[/tex], [tex]|{\boldsymbol{P({X}_{0})}}|=2^1=2[/tex]
Ipotesi induttiva:
[tex]P(k):= {X}_{k} \neq \emptyset[/tex], [tex]|{{X}_{k}}|=k[/tex], [tex]|{\boldsymbol{P({X}_{k})}}|=2^k[/tex]
Ora supposto vera [tex]\forall k P(k)[/tex] dimostro che [tex]P(K) \Rightarrow P(k+1)[/tex]
[tex]P(k+1):= {X}_{k+1} \neq \emptyset[/tex], [tex]|{{X}_{k+1}}|=k+1[/tex],
[tex]|{\boldsymbol{P({X}_{k+1})}}|=2^{|{{X}_{k}}|+1}=2^{k+1}=2^{(k+1)}[/tex]
Non mi convince più di tanto questa dimostrazione, mi sembra fin troppo semplice... è il modo corretto di dimostrare il tutto? La dimostrazione termina qua?
Innanzitutto vi ringrazio per l'attenzione e vi chiedo cortesemente di indicarmi se sto procedendo nel modo corretto a dimostrare i quesiti proposti.
Ho provato a risolvere i seguente esercizi sul principio di induzione riguardo il quale riservo ancora qualche dubbio in fase di dimostrazione...
1)Provare che [tex]\forall n \geq 1[/tex], [tex]5 \mid {2}^{4n}-1[/tex].
2) Provare che [tex]\forall n \geq 4[/tex], [tex]n! > 2^{n}[/tex].
3) Provare che [tex]\forall n \geq 1[/tex], [tex]3 \mid {(n-1)}^3+n^{3}+{(n+1)}^3[/tex].
4) Provare che l'insieme delle parti [tex]|{\boldsymbol{P(X)}}|[/tex] di un insieme finito [tex]X[/tex] di cardinalità [tex]n[/tex](con [tex]n \geq 1[/tex]) ha [tex]2^{n}[/tex] elementi.
1)
Devo dimostrare che [tex]\forall n \geq 1[/tex][tex]\exists q : {2}^{4n}-1=5q[/tex], [tex]n,q \in \mathbb{N}[/tex]
Base dell'induzione:
[tex]P(1):= 2^{4}-1=5q \Leftrightarrow 16-1=5q \Leftrightarrow 15=5q[/tex]
Ipotesi induttiva:
[tex]P(k):= \forall k \geq 1[/tex][tex]\exists h : 2^{4k}-1=5h[/tex]
Ora supposto vera [tex]\forall k P(k)[/tex] dimostro che [tex]P(K) \Rightarrow P(k+1)[/tex]
[tex]2^{4(k+1)}-1 5q[/tex]
[tex]2^{4k}2^{4}-1=5q[/tex]
dalla [tex]P(k)[/tex] ottengo che [tex]2^{4k}=5h+1[/tex] e quindi
[tex](5h+1)2^{4}-1=5q[/tex]
[tex]5[/tex] [tex]2^{4}h+15=5q[/tex]
[tex]5(2^{4}h+3)=5q[/tex]
concludo quindi che avendo dimostrato [tex]P(k+1)[/tex] allora [tex]\forall n P(n)[/tex].
2)
Devo dimostrare che [tex]\forall n \geq 4[/tex], [tex]n! > 2^{n}[/tex].
Base dell'induzione:
[tex]P(4) := 4! > 2^{4} \Leftrightarrow 24 > 16[/tex] vera
Ipotesi induttiva:
[tex]P(k) : = k!>2^{k}[/tex]
Ora supposto vera [tex]\forall k P(k)[/tex] dimostro che [tex]P(K) \Rightarrow P(k+1)[/tex]
[tex]P(k+1):= (k+1)!>2^{(k+1)}[/tex]
moltiplicando la [tex]P(k)[/tex] a destra e a sinistra per [tex](n+1)[/tex] ottengo che
[tex](k+1)k!>2^{k}(k+1)[/tex]
considerando il membro destro della soprastante ed il membro destro della [tex]P(k+1)[/tex] ottengo che
[tex]2^{k}(k+1)>2^{k+1}[/tex]
[tex]k+1>2[/tex]
[tex]k>1[/tex] [tex]\forall k[/tex] essendo per definizione [tex]k\geq4[/tex]
quindi [tex](k+1)!>2^{k}(k+1)>2^{k+1} \Rightarrow (k+1)!>2^{k+1}[/tex] e quindi vera [tex]P(k+1)[/tex] e dimostrata [tex]\forall n P(n)[/tex].
3)
Devo dimostrare che [tex]\forall n \geq 1[/tex][tex]\exists q: (n-1)^3+n^3+(n+1)^3=3q[/tex]
Base dell'induzione:
[tex]P(1):= (1-1)^3+1^3+(1+1)^3=3q \Leftrightarrow 1+8=3q \Leftrightarrow 9=3q[/tex] vera
Ipotesi induttiva:
[tex]P(k):= \forall k \geq 1[/tex][tex]\exists h : (k-1)^3+k^3+(k+1)^3=3h[/tex]
Ora supposto vera [tex]\forall k P(k)[/tex] dimostro che [tex]P(K) \Rightarrow P(k+1)[/tex]
[tex]((k+1)-1)^3+(k+1)^3+((k+1)+1)^3=3q[/tex]
[tex]k^3+(k+1)^3+(k+2)^3=3q[/tex]
riprendendo la [tex]P(k)[/tex] ottengo che [tex]k^3+(k+1)^3=3h-(k+1)^3[/tex]
quindi ponendo quanto ottenuto nella [tex]P(k+1)[/tex] ottengo
[tex]3h-(k-1)^3+(k+2)^3=3q[/tex]
[tex]3h-(k^3-1-3k^2+3k)+(k^3+8+6k^2+12k)=3q[/tex]
[tex]3h-k^3+1+3k^2-3k+k^3+8+6k^2+12k=3q[/tex]
[tex]3h+9k^2+9k+9=3q[/tex]
[tex]3(h+3k^2+3k+3)=3q[/tex]
quindi ho dimostrato che [tex]\forall k P(k) \Rightarrow P(k+1)[/tex] e quindi che [tex]\forall n P(n)[/tex].
4)
Per tale quesito devo dimostrare che [tex]\forall n \geq 1[/tex] se [tex]|{X}|=n[/tex] allora [tex]|{\boldsymbol{P(X)}}|=2^{n}[/tex]
Base dell'induzione:
[tex]P(1):= {X}_{0} \neq \emptyset[/tex], [tex]|{{X}_{0}}|=1[/tex], [tex]|{\boldsymbol{P({X}_{0})}}|=2^1=2[/tex]
Ipotesi induttiva:
[tex]P(k):= {X}_{k} \neq \emptyset[/tex], [tex]|{{X}_{k}}|=k[/tex], [tex]|{\boldsymbol{P({X}_{k})}}|=2^k[/tex]
Ora supposto vera [tex]\forall k P(k)[/tex] dimostro che [tex]P(K) \Rightarrow P(k+1)[/tex]
[tex]P(k+1):= {X}_{k+1} \neq \emptyset[/tex], [tex]|{{X}_{k+1}}|=k+1[/tex],
[tex]|{\boldsymbol{P({X}_{k+1})}}|=2^{|{{X}_{k}}|+1}=2^{k+1}=2^{(k+1)}[/tex]
Non mi convince più di tanto questa dimostrazione, mi sembra fin troppo semplice... è il modo corretto di dimostrare il tutto? La dimostrazione termina qua?
Innanzitutto vi ringrazio per l'attenzione e vi chiedo cortesemente di indicarmi se sto procedendo nel modo corretto a dimostrare i quesiti proposti.
Risposte
Up!
I primi tre esercizi mi sembrano giusti...
Il quarto in linea di massima va bene, però forse la spiegazione è un po' troppo stringata. In particolare, prova a spiegare in modo un po' più esteso perché vale $ | \mathcal{P} ( X_{k+1}) | = 2^{| X_k| +1}.$
Il quarto in linea di massima va bene, però forse la spiegazione è un po' troppo stringata. In particolare, prova a spiegare in modo un po' più esteso perché vale $ | \mathcal{P} ( X_{k+1}) | = 2^{| X_k| +1}.$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo