\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[catalan]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{top=25mm}

\author{Adrià Vilanova Martínez\vspace{-2ex}}
\title{Problemes entregables de Fonaments de la matemàtica\vspace{-2ex}}
%\date{}

\setlength{\parskip}{1em}
\newcommand*{\QEDB}{\hfill\ensuremath{\square}}%
\begin{document}
\maketitle

\textbf{Prob. 1.17. Considerem un enter $m$ i un nombre natural qualsevol $n$. Demostreu que $m^n$ és senar si, i només si, $m$ és senar.}

Estem intentant demostrar un bicondicional, que es podria expresar com: \[m, n \in \mathbb{N}, m^n \equiv 1 \mod 2 \iff m \equiv 1 \mod 2\]

Primer demostrarem el cas $m \equiv 1 \mod 2 \implies m^n \equiv 1 \mod 2$:

Com suposem que $m$ és un nombre natural, té una representació única en factors primers. A més a més, si $m$ és congruent amb 1 mòdul 2 (és senar), això significa que $m$ no és múltiple de 2 (si ho fos, seria congruent amb 0), i a la seva descomposició en factors primers no hi és el 2.

Així doncs, podríem expressar el nombre amb la seva descomposició en factors primers de la següent manera: \[m = p_0^{\beta_0} \cdot p_1^{\beta_1} \cdot ... \cdot p_k^{\beta_k} \: \forall \: p_i \neq 2, \beta_i \in \mathbb{N} \setminus \{0\}\]

A l'elevar aquest nombre a la n-ésima potència, obtindrem la següent expressió: \[m^n = (p_0^{\beta_0} \cdot p_1^{\beta_1} \cdot ... \cdot p_k^{\beta_k})^n =\]\[ = (p_0^{\beta_0})^n \cdot (p_1^{\beta_1})^n \cdot ... \cdot (p_k^{\beta_k})^n =\]\[ = p_0^{\beta_0 n} \cdot p_1^{\beta_1 n} \cdot ... \cdot p_k^{\beta_k n}\]

El que sabem és que cap $p_i$ és 2, llavors a $m^n$ tampoc obtenim cap factor primer que sigui 2. És a dir, $m^n$ no és múltiple de 2 i per tant és senar.

Ara demostrarem el cas $m^n \equiv 1 \mod 2 \implies m \equiv 1 \mod 2$:

Utilitzarem el mateix raonament que pel primer cas però a la inversa. Com $m$ és un nombre natural, $m^n$ també ho és, i el podem expressar com la representació en factors primers de $m$ a la n-éssima potència (no té cap factor 2, ja que $m^n$ es senar):

\[m^n = p_0^{\beta_0 n} \cdot p_1^{\beta_1 n} \cdot ... \cdot p_k^{\beta_k n} \: \forall \: p_i \neq 2, \beta_i \in \mathbb{N} \setminus \{0\}\]

Llavors \[m = (m^n)^\frac{1}{n} = (m^n = p_0^{\beta_0 n} \cdot p_1^{\beta_1 n} \cdot ... \cdot p_k^{\beta_k n})^\frac{1}{n} = \]\[ = p_0^{\beta_0 n \frac{1}{n}} \cdot p_1^{\beta_1 n \frac{1}{n}} \cdot ... \cdot p_k^{\beta_k n \frac{1}{n}} = p_0^{\beta_0} \cdot p_1^{\beta_1} \cdot ... \cdot p_k^{\beta_k}\]

Com els factors són idèntics (exceptuant que es repeteixen només un $\frac{1}{n}$ de les vegades que es repeteixen a $m^n$), tampoc tenim un 2 a la representació en factors primers de $m$, i per tant $m$ no és múltiple de 2, és a dir, és senar.

Habent demostrat els dos casos, queda demostrat l'enunciat aplicant la regla lògica de la introducció del bicondicional. \QEDB

\textbf{Prob. 1.14. Sigui $a_0, a_1, ..., a_n$ una seqüència de nombres. La suma $\sum^n_{i=1} (a_i-a_{i-1})$ s'anomena sèrie telescòpica.}

\textbf{a) Demostreu per inducció que $\sum^n_{i=1} (a_i-a_{i-1}) = a_n - a_0$.}

Primer veurem que el cas base ($n=1$) funciona:

Per definició del sumatori, $\sum^1_{i=1} (a_i - a_{i-1}) = a_1 - a_0$ i segons la hipòtesi d'inducció $\sum^1_{i=1} = a_1 - a_0$, així que es compleix per $n=1$.

Ara suposarem que és certa la hipòtesi d'inducció per a $n=k$ i intentarem veure que també és cert per $n=k+1$.

Llavors la hipòtesi d'inducció (que podem suposar certa) és que $\sum^k_{i=1} (a_i-a_{i-1}) = a_k - a_0$, i amb aquesta voldríem veure que és cert $\sum^{k+1}_{i=1} (a_i-a_{i-1}) = a_{k+1} - a_0$.

Per tal d'utilitzar la hipòtesi d'inducció podem separar el sumatori en dos: \[\sum^{k+1}_{i=1} (a_i-a_{i-1}) = \sum^{k}_{i=1} (a_i-a_{i-1}) + \sum^{k+1}_{i=k+1} (a_i-a_{i-1}) = \sum^{k}_{i=1} (a_i-a_{i-1}) + a_{k+1} - a_k \stackrel{H.I.}{=} \]\[ = a_k - a_0 + a_{k+1} - a_k = a_{k+1} - a_0\]

Hem vist que si la hipòtesi d'inducció es compleix per $n=k$ també ho fa per $n=k+1$, i per tant es demostra (per inducció) l'enunciat per tots els nombres naturals $n$. \QEDB

\textbf{b) Feu servir la identitat $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$ i la fòrmula de la suma de la sèrie telescòpica per evaluar $\sum^n_{i=1} \frac{1}{i(i+1)}$.}

\[\sum^n_{i=1} \frac{1}{i(i+1)} = \sum^n_{i=1} \left(\frac{1}{i} - \frac{1}{i+1}\right)\]

Si diem $a_i = \frac{1}{i+1}$, obtindrem: \[\sum^n_{i=1} \frac{1}{i(i+1)} = \sum^n_{i=1} (a_{i-1} - a_i) = - \sum^n_{i=1} (a_i - a_{i-1}) \stackrel{\text{Suma tel.}}{=} - (a_n - a_0) = \]\[ = a_0 - a_n = \frac{1}{0+1} - \frac{1}{n+1} = 1 - \frac{1}{n+1} = \frac{n}{n+1}\]

Així doncs: \[\sum^n_{i=1} \frac{1}{i(i+1)} = \frac{n}{n+1}\]

\textbf{c) Feu servir la identitat $\frac{1}{k^2-1} = \frac{1}{2}\left(\frac{1}{k-1} - \frac{1}{k+1}\right)$ i la fòrmula de la suma de la sèrie telescòpica per evaluar $\sum^n_{i=2} \frac{1}{i^2-1}$.}

\[\sum^n_{i=2} \frac{1}{i^2-1} = \frac{1}{2}\sum^n_{i=2} \left(\frac{1}{i-1} - \frac{1}{i+1}\right) = \frac{1}{2} \left( \sum^n_{i=2} \frac{1}{i-1} - \sum^n_{i=2} \frac{1}{i+1} \right) = \]

A partir d'aquí hi ha dues maneres de proseguir. La primera s'adequa al que el problema demana (utilitzar la fòrmula de la suma de la sèrie telescòpica), però la segona em sembla molt més natural i prescindeix de la fòrmula de la suma de la sèrie telescòpica perquè directament elimina els termes telescòpics.

Camí 1 (utilitzant fòrmula de la suma de la sèrie tel.):

\[ = \frac{1}{2} \left( \sum^{n-1}_{i=1} \frac{1}{i} - \sum^n_{i=2} \frac{1}{i+1} \right) = \frac{1}{2} \left( 1 + \sum^{n-1}_{i=2} \frac{1}{i} - \sum^{n-1}_{i=2} \frac{1}{i+1} - \frac{1}{n+1} \right) = \] \[ = \frac{1}{2} \left( 1 + \sum^{n-1}_{i=2} \left(\frac{1}{i} - \frac{1}{i+1}\right) - \frac{1}{n+1} \right) = \frac{1}{2} \left( 1 - \sum^{n-1}_{i=2} \left(\frac{1}{i+1} - \frac{1}{i}\right) - \frac{1}{n+1} \right) = \]\[ = \frac{1}{2} \left( 1 - \sum^{n-2}_{i=1} \left(\frac{1}{i+2} - \frac{1}{i+1}\right) - \frac{1}{n+1} \right) \stackrel{\text{S. tel.}}{=} \frac{1}{2} \left( 1 - \left(\frac{1}{n} - \frac{1}{2}\right) - \frac{1}{n+1} \right) = \]\[ = \frac{1}{2} \left( 1 - \frac{1}{n} + \frac{1}{2} - \frac{1}{n+1} \right) = \]

Camí 2 (més natural i directe):

\[ = \frac{1}{2} \left( \sum^{n-2}_{i=0} \frac{1}{i+1} - \sum^n_{i=2} \frac{1}{i+1} \right) = \frac{1}{2} \left( \sum^{1}_{i=0} \frac{1}{i+1} + \sum^{n-2}_{i=2} \frac{1}{i+1} - \sum^{n-2}_{i=2} \frac{1}{i+1} - \sum^n_{i=n-1} \frac{1}{i+1} \right) = \]\[ = \frac{1}{2} \left( \sum^{1}_{i=0} \frac{1}{i+1} - \sum^n_{i=n-1} \frac{1}{i+1} \right) = \frac{1}{2} \left( 1 + \frac{1}{2} - \frac{1}{n} - \frac{1}{n+1} \right) = \]

Ara podem seguir des de qualsevol dels dos camins simplificant l'expressió resultant per arribar a evaluar-la completament:

\[ = \frac{1}{2} \left( \frac{3}{2} - \frac{2n + 1}{n(n+1)} \right) = \frac{3}{4} - \frac{2n + 1}{2n(n+1)}\]

\textbf{d) Sumeu ambdós costats de la identitat $(i+1)^2 - i^2 = 2i + 1$ des de $i = 1$ fins a $i = n$ i feu servir la fórmula de la suma de la sèrie telescòpica per calcular $\sum^n_{i=1}i$.}

\[\sum^n_{i=1} ((i^2 + 1)^2 - i^2) = \sum^n_{i=1} (2i + 1)  \stackrel{\text{S. Tel.}}{\iff} (n+1)^2 - 1^2 = \sum^n_{i=1} (2i + 1) \iff\]\[n^2 + 2n + 1 - 1 = 2\sum^n_{i=1}i + \sum^n_{i=1}1 \iff n^2 + 2n = 2\sum^n_{i=1}i + n \iff\]\[n^2 + n = 2 \sum^n_{i=1}i \iff \sum^n_{i=1} = \frac{n^2+n}{2} \iff \sum^n_{i=1} = \frac{n(n+1)}{2}\]

\textbf{e) Trobeu una fòrmula per a $\sum^n_{i=1} i^2$ mitjançant una tècnica similar a la de l'apartat anterior.}

Com a l'apartat anterior podíem observar que a l'expandre el quadrat de la suma de la part esquerra de l'equació es cancelen els termes de grau 2, podríem posar $(i+1)^3 - i^3$ a la part esquerra de l'equació per aquest apartat perquè al sumar a l'esquerra podríem utilitzar la fòrmula de la suma telescòpica i a la dreta ens quedarien termes de grau igual o menor a 2: el de grau 2 ens interesa per aillar el sumatori de $i^2$, el de grau 1 el sabem calcular amb la fòrmula que hem determinat a l'apartat anterior i el de grau 0 també el sabem calcular ja que és una constant.

\[(i+1)^3 - i^3 = 3i^2 + 3i + 1 \iff \sum^n_{i=1}((i+1)^3 - i^3) = \sum^n_{i=1}(3i^2 + 3i + 1) \stackrel{\text{S. Tel.}}{\iff}\]\[(n+1)^3 - 1^3 = \sum^n_{i=1}(3i^2 + 3i + 1) \iff n^3 + 3n^2 + 3n + 1 - 1 = 3\sum^n_{i=1}i^2 + 3\sum^n_{i=1}i + \sum^n_{i=1}1 \iff\]\[n^3 + 3n^2 + 3n = 3\sum^n_{i=1}i^2 + 3\frac{n(n+1)}{2} + n \iff n^3 + 3n^2 + 2n = 3\sum^n_{i=1}i^2 + 3\frac{n^2+n}{2} \iff\]\[n^3 + 3n^2 + 2n = 3\sum^n_{i=1}i^2 + \frac{3}{2}n^2 + \frac{3}{2}n \iff 3\sum^n_{i=1}i^2 = n^3 + \frac{3}{2}n^2 + \frac{1}{2}n \iff\]\[3\sum^n_{i=1}i^2 = \frac{2n^3 + 3n^2 + n}{2} \iff \sum^n_{i=1}i^2 = \frac{2n^3 + 3n^2 + n}{6} \iff\]\[\sum^n_{i=1}i^2 = \frac{2n(n+1)(n+\frac{1}{2})}{6} \iff \sum^n_{i=1}i^2 = \frac{n(n+1)(2n+1)}{6}\]

\end{document}