2 Ottobre

Aritmetica 2014/2015
Esercizi svolti in classe
2 Ottobre
1
Definizioni, notazione
1. I numeri interi positivi pari si indicano con 2N. Analogamente, gli interi
pari si indicano con 2Z.
2. a divide b si indica anche con a | b.
3. Definizione. Per ogni n, k ∈ N
n
n!
=
k!(n − k)!
k
4. Definizione. Per ogni n, i, j ∈ N
n
i, j
=
n!
i!j!
5. Notiamo che se abbiamo una sequenza di n oggetti
a1 , . . . , an
le coppie simmetriche rispetto al centro della sequenza sono
(1, n), (2, n − 1), . . . , (j, n − j + 1)
con j = 1, . . . , m sia se ∃ m ∈ N t.c. n = 2m + 1 (n dispari) sia se
∃ m ∈ N t.c. n = 2m (n pari).
2
Esercizi svolti
1. Sia a ∈ R e n ∈ N. Vediamo una dimostrazione per induzione forte
sbagliata che n ≥ 1 =⇒ an−1 = 1.
Proposizione P (n) = n ≥ 1 =⇒ an−1 = 1.
Caso Base: n = 1; an−1 = a0 = 1. Caso base OK.
1
Passo induttivo: dato P (n) dimostriamo P (n + 1).
Vogliamo dimostrare che an+1−1 = 1 se n ≥ 1 e sapendo che an−1 = 1.
Dato che
1·1
an−1 · an−1
=
a(n+1)−1 = an =
n−2
a
1
dato che per ipotesi induttiva an−1 = 1 e an−2 = 1.
L’errore e’ nella base: l’ipotesi induttiva funziona se n > 2. Se n = 2
0 0
·a
, relazione vera ma non possiamo
nella dimostrazione abbiamo a = aa−1
−1
applicare l’ipotesi induttiva ad a = a1 in generale diverso da 1. Quindi il
caso base deve essere n = 2, e qui la tesi `e in generale falsa, a2−1 = a1 = a.
Abbiamo pero’ dimostrato che se a = 1, n ≥ 1 =⇒ an−1 = 1. Cosa
peraltro gi`
a forse nota.
2. Per ogni n ∈ N il numero n3 + 3n2 + 5n `e divisibile per 3, [scriviamo anche
3 | (n3 + 3n2 + 5n)].
Usiamo l’induzione su n con proposizione P (n) = 3 | (n3 + 3n2 + 5n).
Base P (0). Per n = 0 abbiamo che 3 | (n3 + 3n2 + 5n) ⇐⇒ 3 | 0.
Passo induttivo: dato n ∈ N da P (n) dimostriamo P (n + 1).
(n + 1)3 + 3(n + 1)2 + 5(n + 1)
=
n3 + 3n2 + 3n + 3 + 3n2 + 6n + 3 + 5n + 5
=
(n3 + 3n2 + 5n) + (3n2 + 9n + 9)
Dato che 3 | (n3 + 3n2 + 5n) per l’ipotesi induttiva e che ovviamente
3 | (3n2 + 9n + 9), 3 divide anche la loro somma, e quindi
3 | [(n + 1)3 + 3(n + 1)2 + 5(n + 1)]
ed abbiamo dimostrato P (n + 1) da P (n).
3. La somma dei primi n numeri interi positivi `e uguale a
n(n+1)
.
2
Quello che dobbiamo dimostrare `e che
∀n∈N
n
X
k=1
k=
n(n + 1)
2
Dimostrazione per induzione:
Pn
”
Dato n ∈ N sia P (n) la proposizione ” k=1 k = n(n+1)
2
P1
1(1+1)
Base: P (1) `e vera, dato che 1 = k=1 k = 2 = 1.
Passo Induttivo: dobbiamo dimostrare che ∀ n ∈ N P (n) =⇒ P (n + 1).
2
n+1
X
k=1
k
=
n
X
k + (n + 1)
k=1
per ipotesi induttiva
n(n + 1)
+ (n + 1)
=
2
(n + 1)(n + 2)
=
2
e quindi P (n + 1) vale se P (n) vale.
Altra dimostrazione:
Supponiamo che n sia pari, cio`e che esista m ∈ N tale che n = 2m.
Abbiamo la somma di 2m elementi
1 + 2 + 3 + · · · + (n − 2) + (n − 1) + n
La somma del primo e ultimo elemento `e uguale a n + 1, come la somma
del secondo e penultimo, 2+n−1 = n+1, terzo e second’ultimo 3+n−2 =
n + 1, etc.etc. Abbiamo che la somme del j-esimo elemento e del n − j + 1esimo elemento `e j + n − j + 1 = n + 1. [Ricordiamo che j varia da 1
a m] Dato che abbiamo 2m addendi, la somma `e guale alla somma di m
volte n + 1, cio`e al prodotto m(n + 1). Ma m = n/2 e quindi abbiamo
dimostrato che
n
X
n(n + 1)
∀ n ∈ 2 N,
k=
2
k=1
Supponiamo che n sia dispari, cio`e che esista m ∈ N tale che n = 2m + 1.
Notiamo che quindi m = n−1
2 . Ripetiamo il ragionamento precedente con
i numeri
1, 2, . . . , m, m + 2, . . . , 2m, 2m + 1
ovvero i numeri da 1 a 2m + 1 escluso m + 1 = n+1
2 in modo da avere due
sequenze consecutive di m numeri, 1, 2, . . . , m e m + 2, . . . 2m, 2m + 1. La
somma delle coppie di numeri simmetrici j, 2m + 1 − j + 1 `e
j + 2m + 1 − j = 2m + 1 + 1 = n + 1
e abbiamo m = n−1
e quindi (n−1)(n+1)
.
2 di queste coppie. La loro somma `
2
Per ottenere la somma dei primi 2m + 1 numeri aggiungiamo a questa
somma il numero non compreso nella seconda sequenza, m + 1 = n+1
2
n(n + 1)
(n − 1)(n + 1) n + 1
+
=
2
2
2
Dato che la tesi vale sia per n pari che per n dispari, vale sempre.
3
4. Teorema del Binomio
Dimostrare che per ogni a, b ∈ R, n ∈ N si ha che
n
(a + b) =
n X
n
k=0
k
an−k bk
Dimostriamo il teorema per induzione. La `e proposizione
n
P (n) = ∀ a, b ∈ R ho (a + b) =
n X
n
k=0
k
an−k bk
Base: P (0) `e facile. Infatti
(a + b)0 = 1 e
0 X
0 0−0 0
0 0 0
a b =
a b =1
k
0
k=0
Passo induttivo: per ogni n ∈ N supponendo P (n) dimostrare P (n + 1).
4
(a + b)n+1
=
(a + b)(a + b)n
per l’ipotesi induttiva
n X
n n−k k
= (a + b)
a
b
k
k=0
n n X
X
n n−k k
n n−k k
= a
a
b +b
a
b
k
k
k=0
k=0
n n X
n n−k+1 k X n n−k k+1
=
a
b +
a
b
k
k
k=0
k=0
togliamo gli estremi dalle sommatorie
n−1 n X
n n−k+1 k X n n−k k+1
n+1
a
b
+ bn+1
a
b +
= a
+
k
k
k=0
k=1
portiamo le sommatorie agli stessi estremi k-¿k-1
n n−1 X
n n−k+1 k X
n
n+1
= a
+
a
b +
an−k+1 bk + bn+1
k
k−1
k=1
k=1
unifichiamo le sommatorie
n X
n n−k+1 k
n
n+1
n−k+1 k
= a
+
a
b +
a
b + bn+1
k
k−1
k=1
raccogliamo i termini uguali
n X
n
n
= an+1 +
+
an−k+1 bk + bn+1
k
k−1
k=1
per le proprieta’ dei binomiali
n X
n + 1 n−k+1 k
n+1
a
b + bn+1
= a
+
k
k=1
n+1
n+1
notiamo che
=1e
=1
0
n+1
n n + 1 n+1 X
n + 1 n−k+1 k
n + 1 n+1
=
a
+
a
b +
b
0
k
n+1
k=1
n+1
X n + 1 =
an+1−k bk
k
k=0
E quest’ultima `e P (n + 1), che abbiamo dimostrato a partire da P (n).
5
3
Esercizi proposti
1. Propriet`
a fondamentale del triangolo di Tartaglia:
n
n
n
=
∀ n, k ∈ N
+
k
k+1
k+1
[Suggerimento: usare la definizione di binomiale]
2. Teorema del Trinomio
Dimostrare che per ogni a, b, c ∈ R, n ∈ N si ha che
X n (a + b + c)n =
ai bj ck
i, j, k
i+j+k=n
3. Teorema dell’m-omio
Dimostrare che per ogni m ∈ N, a1 , . . . , am ∈ R, n ∈ N si ha che
X
n
n
(a1 + · · · + am ) =
ai11 · · · aimm
i
,
.
.
.
,
i
1
m
i +···+i =n
1
m
4. Dimostrare che per ogni n ∈ N si ha
n
X
k2 =
k=1
n(n + 1)(2n + 1)
6
5. Dimostrare che per ogni n ∈ N si ha
2
n
X
n(n + 1)
3
k =
2
k=1
6. Trovare una formula per la somma delle potenze quarte.
7. Trovare una formula per la somma delle potenze quinte.
8. Trovare una formula per la somma delle potenze i-esime.
9. Sia a ∈ R − {1}. Dimostrare che
∀n∈N
n
X
ak =
k=0
an − 1
a−1
10. Dimostrare o confutare
n
∀n∈N
2
X
1
6
=2−
1
n

Download Report