Esercizi sul principio di induzione

[Howard_Wolowitz]

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 \( \displaystyle \forall n \geq 1 \) , \( \displaystyle 5 \mid {2}^{4n}-1 \) .
2) Provare che \( \displaystyle \forall n \geq 4 \) , \( \displaystyle n! > 2^{n} \) .
3) Provare che \( \displaystyle \forall n \geq 1 \) , \( \displaystyle 3 \mid {(n-1)}^3+n^{3}+{(n+1)}^3 \) .
4) Provare che l'insieme delle parti \( \displaystyle |{\boldsymbol{P(X)}}| \) di un insieme finito \( \displaystyle X \) di cardinalità \( \displaystyle n \) (con \( \displaystyle n \geq 1 \) ) ha \( \displaystyle 2^{n} \) elementi.
1)
Devo dimostrare che \( \displaystyle \forall n \geq 1 \) \( \displaystyle \exists q : {2}^{4n}-1=5q \) , \( \displaystyle n,q \in \mathbb{N} \)
Base dell'induzione:
\( \displaystyle P(1):= 2^{4}-1=5q \Leftrightarrow 16-1=5q \Leftrightarrow 15=5q \)
Ipotesi induttiva:
\( \displaystyle P(k):= \forall k \geq 1 \) \( \displaystyle \exists h : 2^{4k}-1=5h \)
Ora supposto vera \( \displaystyle \forall k P(k) \) dimostro che \( \displaystyle P(K) \Rightarrow P(k+1) \)
\( \displaystyle 2^{4(k+1)}-1 5q \)
\( \displaystyle 2^{4k}2^{4}-1=5q \)
dalla \( \displaystyle P(k) \) ottengo che \( \displaystyle 2^{4k}=5h+1 \) e quindi
\( \displaystyle (5h+1)2^{4}-1=5q \)
\( \displaystyle 5 \) \( \displaystyle 2^{4}h+15=5q \)
\( \displaystyle 5(2^{4}h+3)=5q \)
concludo quindi che avendo dimostrato \( \displaystyle P(k+1) \) allora \( \displaystyle \forall n P(n) \) .
2)
Devo dimostrare che \( \displaystyle \forall n \geq 4 \) , \( \displaystyle n! > 2^{n} \) .
Base dell'induzione:
\( \displaystyle P(4) := 4! > 2^{4} \Leftrightarrow 24 > 16 \) vera
Ipotesi induttiva:
\( \displaystyle P(k) : = k!>2^{k} \)
Ora supposto vera \( \displaystyle \forall k P(k) \) dimostro che \( \displaystyle P(K) \Rightarrow P(k+1) \)
\( \displaystyle P(k+1):= (k+1)!>2^{(k+1)} \)
moltiplicando la \( \displaystyle P(k) \) a destra e a sinistra per \( \displaystyle (n+1) \) ottengo che
\( \displaystyle (k+1)k!>2^{k}(k+1) \)
considerando il membro destro della soprastante ed il membro destro della \( \displaystyle P(k+1) \) ottengo che
\( \displaystyle 2^{k}(k+1)>2^{k+1} \)
\( \displaystyle k+1>2 \)
\( \displaystyle k>1 \) \( \displaystyle \forall k \) essendo per definizione \( \displaystyle k\geq4 \)
quindi \( \displaystyle (k+1)!>2^{k}(k+1)>2^{k+1} \Rightarrow (k+1)!>2^{k+1} \) e quindi vera \( \displaystyle P(k+1) \) e dimostrata \( \displaystyle \forall n P(n) \) .
3)
Devo dimostrare che \( \displaystyle \forall n \geq 1 \) \( \displaystyle \exists q: (n-1)^3+n^3+(n+1)^3=3q \)
Base dell'induzione:
\( \displaystyle P(1):= (1-1)^3+1^3+(1+1)^3=3q \Leftrightarrow 1+8=3q \Leftrightarrow 9=3q \) vera
Ipotesi induttiva:
\( \displaystyle P(k):= \forall k \geq 1 \) \( \displaystyle \exists h : (k-1)^3+k^3+(k+1)^3=3h \)
Ora supposto vera \( \displaystyle \forall k P(k) \) dimostro che \( \displaystyle P(K) \Rightarrow P(k+1) \)
\( \displaystyle ((k+1)-1)^3+(k+1)^3+((k+1)+1)^3=3q \)
\( \displaystyle k^3+(k+1)^3+(k+2)^3=3q \)
riprendendo la \( \displaystyle P(k) \) ottengo che \( \displaystyle k^3+(k+1)^3=3h-(k+1)^3 \)
quindi ponendo quanto ottenuto nella \( \displaystyle P(k+1) \) ottengo
\( \displaystyle 3h-(k-1)^3+(k+2)^3=3q \)
\( \displaystyle 3h-(k^3-1-3k^2+3k)+(k^3+8+6k^2+12k)=3q \)
\( \displaystyle 3h-k^3+1+3k^2-3k+k^3+8+6k^2+12k=3q \)
\( \displaystyle 3h+9k^2+9k+9=3q \)
\( \displaystyle 3(h+3k^2+3k+3)=3q \)
quindi ho dimostrato che \( \displaystyle \forall k P(k) \Rightarrow P(k+1) \) e quindi che \( \displaystyle \forall n P(n) \) .
4)
Per tale quesito devo dimostrare che \( \displaystyle \forall n \geq 1 \) se \( \displaystyle |{X}|=n \) allora \( \displaystyle |{\boldsymbol{P(X)}}|=2^{n} \)
Base dell'induzione:
\( \displaystyle P(1):= {X}_{0} \neq \emptyset \) , \( \displaystyle |{{X}_{0}}|=1 \) , \( \displaystyle |{\boldsymbol{P({X}_{0})}}|=2^1=2 \)
Ipotesi induttiva:
\( \displaystyle P(k):= {X}_{k} \neq \emptyset \) , \( \displaystyle |{{X}_{k}}|=k \) , \( \displaystyle |{\boldsymbol{P({X}_{k})}}|=2^k \)
Ora supposto vera \( \displaystyle \forall k P(k) \) dimostro che \( \displaystyle P(K) \Rightarrow P(k+1) \)
\( \displaystyle P(k+1):= {X}_{k+1} \neq \emptyset \) , \( \displaystyle |{{X}_{k+1}}|=k+1 \) ,
\( \displaystyle |{\boldsymbol{P({X}_{k+1})}}|=2^{|{{X}_{k}}|+1}=2^{k+1}=2^{(k+1)} \)
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.

[Howard_Wolowitz]

Up!

[Pappappero]

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 \( \displaystyle {\left|{\mathcal{{{P}}}}{\left({X}_{{{k}+{1}}}\right)}\right|}={{2}}^{{{\left|{X}_{{k}}\right|}+{1}}}. \)