Soluzioni proposte

Soluzione dell'esercizio 1 Procediamo per induzione su $n$. Sia $n=1$, dato che, $F_3=2$ e $F_1=F_2=1$, si ha $\sum_{i=1}^1 F_i=F_1=1=2-1=F_3-1$.

Supponiamo la tesi vera per $n$ e proviamola per $n+1$.

$$\sum_{i=1}^{n+1}F_i=\sum_{i=1}^{n}F_i+F_{n+1}=F_{n}-1+F_{n+1}=F_{n+3}-1$$

dove la seconda uguaglianza segue dall'ipotesi di induzione, e l'ultima dalla definizione dei numeri di Fibonacci.     

Soluzione dell'esercizio 2 Poiché $87\cong3\quad{\rm mod}\ 84$, la seconda congruenza è equivalente a $x \cong 3 \quad{\rm mod}\ 84$, e quindi il sistema equivale a:

$$\left\{ \begin{array}{ll} x \cong 2 &\quad{\rm mod}\ 113 \\ x \cong 3 &\quad{\rm mod}\ 84 \end{array}\right.$$

Tale sistema ha soluzione se e solo se $(113,84)\mathrel{\big\vert}(3-2)=1$. Usiamo l'algoritmo di Euclide per il calcolo del M.C.D. tra $113$ e $84$.

$$\begin{array}{rcl} 113 & = & 84 \cdot 1 + 29 \\ 84 & = & 29... ...+ 2 \\ 3 & = & 2 \cdot 1 + 1 \\ 2 & = & 1 \cdot 2 \end{array}$$

quindi $(113,84)=1$ e pertanto il sistema è risolubile.

Esprimiamo $1$ come combinazione intera di $113$ e $84$.

$$\begin{array}{rclcrcl} 29 & = & 113 - 8 4 & \qquad & 29 & = ... ... 1 & = & 3 - 2 & \qquad & 1 & = & 113(29) + 84(-39) \end{array}$$

Quindi,

$$3-2 = 1 = 113(29) + 84(-39)$$

da cui

$$3 + 84 \cdot 39 = 2 + 113 \cdot 29 = 3279$$

è una soluzione del sistema di congruenze. L'insieme delle soluzioni è allora dato da

$$\{3279 + k [113,84]\mid k\in\mathbb{Z}\}= \{3279 + k 113\cdot 84 \mid k\in\mathbb{Z}\}.$$

    

Soluzione dell'esercizio 3 L'operazione è associativa. Infatti:

$$\begin{array}{rcl} x * (y * z) &= &x * (y+z-yz) = x + (y+z-y... ...+y-xy) + z -(x+y-xy)z=\\ &=&x+y-xy +z -xz -yz +xyz \end{array}$$

e quindi, $x * (y * z)=(x * y) * z$ per ogni $x,y,z\in\mathbb{Q}$, ovvero $(\mathbb{Q},*)$ è un semigruppo.

C'è l'elemento neutro. Infatti:

$$x*0=x+0-x0=x$$

Osserviamo che $x*y=y*x$ per ogni $x,y$ e quindi anche $0*x=x$. Pertanto $(\mathbb{Q}.*)$ è un monoide.

$(\mathbb{Q}.*)$ non è un gruppo, dato che $1$ non ha inverso. Infatti per ogni $x\in\mathbb{Q}$ si ha:

$$1*x=1+x-1\cdot x=1+x-x=1\ne 0.$$

    

Soluzione dell'esercizio 4 Denotiamo $G=\{\sigma\in S_n\mid \sigma(1)=1\}$. Ovviamente la permutazione identica $(1)\in G$, dato che fissa tutti gli elementi. Siano $\sigma,\tau\in G$ allora, dato che $\sigma(1)=1$ e $\tau(1)=1$ anche $\tau^{-1}(1)=1$ e quindi:

$$\sigma\tau^{-1}(1)=\sigma(\tau^{-1}(1))=\sigma(1)=1$$

ossia $\sigma\tau^{-1}\in G$, quindi, per il criterio del sottogruppo, $G$ è un sottogruppo di $S_n$.     

Soluzione dell'esercizio 5 L'operazione è associativa. Infatti:

$$\begin{array}{rcl} ((a,b)(c,d))(e,f)&=&(ac, ad+b)(e,f)=(ace,... ...f))&=&(a,b)(ce,cf+d)=(ace,a(cf+d)+b)=(ace,acf+ad+b) \end{array}$$

$(1,0)$ è unità sinistra e destra. Infatti

$$\begin{array}{rcl} (1,0)(a,b)&=&(1a,1b+0)=(a,b)\\ (a,b)(1,0)&=&(a1,a0+b)=(a,b) \end{array}$$

Ogni elemento è invertibile. Infatti se $(a,b)\in G$ allora $(a^{-1},-a^{-1}b)\in G$ e

$$\begin{array}{rcl} (a,b)(a^{-1},-a^{-1}b)&=&(aa^{-1},-aa^{-1... ...1},-a^{-1}b)(a,b)&=&(a^{-1}a,a^{-1}b-a^{-1}b)=(1,0) \end{array}$$

$X_1$ è un sottogruppo. Infatti, $(1,0)\in G$. Inoltre se $(1,a),(1,b)\in G$ allora

$$(1,a)(1,b)^{-1}=(1,a)(1,-b)=(1,a-b)\in G$$

si conclude per il criterio del sottogruppo.

$X_2$ non è sottogruppo. Infatti non è chiuso per l'operazione. Ad esempio $(1/2,0),(1,1)\in X_2$ ma $(1/2,0)(1,1)=1/2,1/2)\notin X_2$.

$X_3$ non è sottogruppo. Infatti non è detto che ogni elemento di $X_3$ abbia inverso in $X_3$. Ad esempio $(2,0)\in X_3$ mentre $(2,0)^{-1}=(1/2,0)\notin X_3$.     

Soluzione dell'esercizio 6 Procediamo per induzione su $n$. Per $n=2$ la tesi segue immediatamente dalla definizione di differenza simmetrica.

Supponiamo la tesi vera per $n$, allora

$$\begin{array}{rcl} A_1\bigtriangleup A_2\bigtriangleup \dots... ...iangleup A_2\bigtriangleup \dots\bigtriangleup A_n) \end{array}$$

Ma ora, per ipotesi di induzione $x\in 1\bigtriangleup A_2\bigtriangleup \dots\bigtriangleup A_n$ se e solo se $x$ sta in numero dispari di $A_i$, quindi

$$\begin{array}{rcl} x\in (A_1\bigtriangleup A_2\bigtriangleup... ...gli $A_1,\dots,A_n$\ e non appartiene a $A_{n+1}$} \end{array}$$

e quindi $x\in A_1\bigtriangleup A_2\bigtriangleup \dots\bigtriangleup A_{n+1}$ se e solo se appartiene a un numero dispari degli $A_1,A_2,\dots, A_{n+1}$