ALGEBRA 1 — A.A. 2020/2021 FOGLIO ESERCIZI 4
FABIO GAVARINI
— ∗ —
NOTA: per ogni insieme finito E, indichiamo con E il numero di elementi di E . [1] — Dimostrare per induzione che
∑n k=0
k = n (n + 1)
2 per ogni n∈ N .
N.B.: si provi ad applicare il principio di induzione in ciascuna delle sue tre forme:
Induzione Debole, Induzione Forte, Principio del Minimo.
[2] — Dimostrare, per induzione, che per ogni n∈ N vale la seguente diseguaglianza:
(n− 3)2 n2+ 11
[3] — Dimostrare, per induzione su n , che il numero An := 32 n+1+ 2n+2 `e multiplo (intero) di 7, per ogni n∈ N .
[4] — Sia E un insieme, e sia P(E) il corrispondente insieme delle parti di E . Di- mostrare — per induzione sul numero |E| di elementi in E — che P(E)= 2|E| .
[5] — Siano A e B due insiemi finiti, BA l’insieme di tutte le funzioni da A a B, e Inj (A, B) il sottoinsieme di tutte le funzioni iniettive da A a B.
Dimostrare che BA=|B||A| e Inj (A, B)=∏|A|−1
s=0
(|B| − s) .
[6] — Convertire in baseDIECI— cio`e riscriverli usando la notazione posizionale in base
DIECI — i numeri n′ e n′′ espressi da n′ := (7503)8 e n′′ := (40213)5 rispettivamente in base 8 e in base 5.
Soluzione: n′ = (3907)10 , n′′ = (2558)10 .
[7] — Sia n := (9873)
DIECI, cio`e n `e il numero naturale che in base DIECI `e espresso dalla scrittura posizionale n = (9873)
DIECI. Scrivere n in base 8 e in base 7.
Soluzione: n = (23221)8 , n = (40533)7 . 1
2 PRINCIPIO DI INDUZIONE, NUMERAZIONE POSIZIONALE
[8] — Conversioni facili (
b br)
: Sia n il numero naturale che in base 2 `e espresso dalla scrittura posizionale n = (11010111011)2. Scrivere n in base 8.
Soluzione: n = (3273)8 .
[9] — Conversioni facili (
bs b)
: Sia n il numero naturale che in base 4 `e espresso dalla scrittura posizionale n = (30213)4. Scrivere n in base 2.
Soluzione: n = (1100100111)2 .
[10] — Conversioni facili (
bs b/
b br)
: Sia n il numero naturale che `e espresso in base 8 dalla scrittura posizionale n = (2351)8. Scrivere n in base 4 e in base 2.
Soluzione: n = (103221)4 , n = (10011101001)2 .
[11] — Usando la scrittura posizionale in base 5, tramite le cinque cifre (ordinate!) 0, 1, 2, 3 e 4, calcolare — senza passare per la scrittura in base DIECI — le somme (1234)5 + (2321)5 e (3421)5 + (4023)5 . Come controprova, risolvere lo stesso prob- lema convertendo prima in base DIECI i numeri da sommare, calcolando la somma usando la scrittura posizionale in base DIECI, e infine convertire in baseDIECI il risultato ottenuto.
Soluzione: (1234)5+ (2321)5 = (4110)5 , (3421)5+ (4023)5 = (12444)5 . Per la controprova, si ha
(1234)5+ (2321)5 = (194)
DIECI + (336)
DIECI = (530)
DIECI = (4110)5 , (3421)5+ (4023)5 = (486)
DIECI+ (513)
DIECI = (999)
DIECI = (12444)5 .
[12] — Usando la scrittura posizionale in base b = DODICI, tramite le dodici cifre (ordinate!) dell’insieme { 0 , 1 , 2 , 3 , . . . , 8 , 9 , ⊥ , ∧ } , calcolare — senza passare per la scrittura in base DIECI... — la somma (70⊥31∧5)b+ (497∧⊥0∧)b .
Soluzione: (70⊥31∧5)b + (497∧⊥0∧)b = (∧⊥63004)b .