4.5: Ejercicios

EJERCICIO 4.1. Demostrar por inducción que 3 divide\(7^{n}-4\) por cada\(n \in \mathbb{N}^{+}\).

EJERCICIO 4.2. Demuestra por inducción que\[(\forall n \in \mathbb{N}) 2^{n}>n .\] EJERCICIO 4.3. Demostrar que cualquier subconjunto de un conjunto bien ordenado es soldado. EJERCICIO 4.4. \((1+x)^{n} \geq 1+n x\)Demuéstralo para todos\(n \in \mathbb{N}^{+}\) y cada uno\(x \in(-1, \infty)\).

EJERCICIO 4.5. Demuestra por inducción que cada conjunto finito de números reales tiene un elemento más grande.

EJERCICIO 4.6. Dejar\(X\) y\(Y\) ser conjuntos con\(n\) elementos cada uno. ¿Cuántas bijecciones de\(X\) a\(Y\) hay? ¿Qué te dice esto sobre el número de permutaciones de\(\ulcorner n\urcorner\)? Demuestre su reclamo.

EJERCICIO 4.7. Los coeficientes binomiales se\(\left(\begin{array}{l}n \\ k\end{array}\right)\) pueden definir a partir del triángulo de Pascal por:

i)\(\forall n \in \mathbb{N},\left(\begin{array}{l}n \\ 0\end{array}\right)=\left(\begin{array}{l}n \\ n\end{array}\right)=1\).

ii)\(\forall 2 \leq n \in \mathbb{N}, \forall 1 \leq k \leq n-1,\left(\begin{array}{l}n \\ k\end{array}\right)=\left(\begin{array}{c}n-1 \\ k\end{array}\right)+\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)\).

Demostrar por inducción que\[\left(\begin{array}{l} n \\ k \end{array}\right)=\frac{n !}{(n-k) ! k !} .\] EXercise 4.8. Demostrar el teorema binomial: con\(\left(\begin{array}{l}n \\ k\end{array}\right)\) definido por el Ejercicio 4.7, para cualquiera\(n \in \mathbb{N}\), la siguiente identidad contiene\[(x+y)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k} .\] Exercise 4.9. Demostrar\(\sum_{k=0}^{n}\left(\begin{array}{l}n \\ k\end{array}\right)=2^{n}\).

EJERCICIO 4.10. Demostrar, para todos\(n \in \mathbb{N}^{+}\),\[\left(\begin{array}{c} 2 n \\ n \end{array}\right) \geq \frac{2^{2 n-1}}{\sqrt{n}}\] EJERCICIO 4.11. El Principio de Descenso dice que no hay una secuencia infinita estrictamente decreciente de números naturales. Demostrar el Principio de Descenso.

EJERCICIO 4.12. Los números de Fibonacci se definen recursivamente por\(F_{1}=1, F_{2}=1\), y para\(n \geq 3, F_{n}=F_{n-1}+F_{n-2}\). Demostrar que los números de Fibonacci vienen dados por la ecuación\[F_{n}=\frac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n} \sqrt{5}} .\] Este es un ejemplo de una fórmula que es difícil de adivinar, pero fácil de verificar. Para una explicación de cómo surge la fórmula, ver Ejercicio 5.29.

EJERCICIO 4.13. \(X\)Sea un conjunto bien ordenado por una relación\(\preceq\). Decimos que una secuencia de elementos en\(X,\left\langle x_{n} \mid n \in \mathbb{N}\right\rangle\), es estrictamente decreciente (con respecto a\(\preceq\)) si para todos\(m, n \in \mathbb{N}\)\[[m<n] \Rightarrow\left[x_{n} \preceq x_{m} \wedge x_{n} \neq x_{m}\right] .\] Demostrar que no hay una secuencia estrictamente decreciente de elementos en\(X\).

EJERCICIO 4.14. Demostrar que el último dígito de\(7^{7} \underbrace{7}\) es 3 para cualquier torre de sietes de altura superior a 1.

EJERCICIO 4.15. Dar otro ejemplo que ilustre la necesidad de un caso base en una prueba válida por inducción.

EJERCICIO 4.16. Supongamos que hay un polinomio de grado 4 en\(N\) que da\(\sum_{n=0}^{N} n^{3}\). Encuentra el polinomio y luego prueba que la fórmula es correcta por inducción.

Usa el método de Arquímedes para demostrar que

EJERCICIO 4.17. Dejar\(\mathbb{N}[x]\) ser el conjunto de polinomios con coeficientes numéricos naturales. Definir una relación\(\preceq\)\(\mathbb{N}[x]\) por:

Vamos\(p(x)=\sum_{n=0}^{N} a_{n} x^{n}\), y\(q(x)=\sum_{n=0}^{M} b_{n} x^{n}\). Decir que\(p \preceq q\) iff, si\(k\) es el coeficiente de grado más alto en el que\(p\) y\(q\) difieren, entonces\(a_{k} \leq b_{k}\). ¿Es\(\preceq\) un ordenamiento lineal? ¿Es un buen orden de\(\mathbb{N}[x]\)?

EJERCICIO 4.18. Supongamos que existe un polinomio\(p\) de grado 5 tal que\[\sum_{n=0}^{N} n^{4}=p(N) .\] Encuentra\(p\) y prueba que la fórmula que propones es correcta.

EJERCICIO 4.19. Determinar el conjunto de números naturales positivos de\(n\) tal manera que la suma de cada número natural\(n\) consecutivo sea divisible por\(n\). EJERCICIO 4.20. Que\(f\) sea una función real tal que, para\(x, y \in \mathbb{R}\),\[f(x+y)=f(x)+f(y) .\] Demostrar que

a)\(f(0)=0\)

b)\(f(n)=n f(1)\).

EJERCICIO 4.21. Demostrar Corolario 4.9.

EJERCICIO 4.22. Considera cajas con dimensiones\(a, b\) y\(c\) en las que se fija la suma de las dimensiones (i.e.\(a+b+c\)). Demostrar que la caja con mayor volumen posible tiene dimensiones que satisfacen\(a=b=c\).

EJERCICIO 4.23. Demostrar por inducción que cualquier declaración proposicional bien formada tiene un valor de verdad bien definido.

EJERCICIO 4.24. Demostrar por inducción en el número de conectivos proposicionales que cada declaración proposicional compuesta es equivalente a una declaración usando solo\(\neg\) y\(\vee\).

EJERCICIO 4.25. Demostrar por inducción en el número de conectivos proposicionales que cada declaración proposicional compuesta es equivalente a una declaración usando solo\(\neg\) y\(\wedge\).

EJERCICIO 4.26. Dejar\(Q_{i}\) ser un cuantificador, para\(1 \leq i \leq n\). Para cada uno\(Q_{i}\), deja\(Q_{i}^{*}\) ser el cuantificador complementario. Es decir, si\(Q_{i}=\forall\), entonces\(Q_{i}^{*}=\exists\); si\(Q_{i}=\exists\), entonces vamos\(Q_{i}^{*}=\forall\). Demostrar por inducción en el número de cuantificadores que,\(\neg\left(Q_{1} x_{1}\right)(\ldots)\left(Q_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right) \equiv\left(Q_{1}^{*} x_{1}\right)(\ldots)\left(Q_{n}^{*} x_{n}\right) \neg P\left(x_{1}, \ldots, x_{n}\right) .\)

EJERCICIO 4.27. Definir el número de\(n^{\text {th }}\) Fermat para que sea\[F_{n}:=2^{2^{n}}+1, \quad n \in \mathbb{N} .\] (i) Mostrar que los números de Fermat satisfacen\[\prod_{k=0}^{n} F_{k}=F_{n+1}-2 .\] (ii) Concluir que dos números Fermat distintos son coprimos. EJERCICIO 4.28. Dejar\(\left\langle a_{n}: n \in \mathbb{N}\right\rangle\) ser una secuencia de números positivos. Supongamos que\(a_{0} \leq 1\), y eso para todos\(N \in \mathbb{N}\),\[a_{N+1} \leq \sum_{n=0}^{N} a_{n} .\] Demuestra\[(\forall N \in \mathbb{N}) a_{n} \leq 2^{N}\] EJERCICIO 4.29. Dejar\(\left\langle a_{n}: n \in \mathbb{N}\right\rangle\) ser una secuencia de números positivos satisfactorios (4.21), y\(a_{0} \leq C\). ¿Cuál es el análogo correcto de (4.22)? Demuestra tu aseveración.

EJERCICIO 4.30. Let\(\mathcal{F}=\left\{X_{\alpha} \mid \alpha \in A\right\}\) Ser una familia indexada de conjuntos disjuntos por pares. Supongamos que cada uno\(X_{\alpha}\) está bien ordenado por\(\preceq_{\alpha}\) y que\(A\) está bien ordenado por\(\preceq\). Definir una relación\(R\) sobre la unión de todos los conjuntos en\(\mathcal{F}\) por: para todos\(a, b \in \bigcup_{\alpha \in A} X_{\alpha}, a R b\) iff (a)\(a \in X_{\alpha_{1}}, b \in X_{\alpha_{2}}\) y\(\alpha_{1} \preceq \alpha_{2}\),

o

b)\((\exists \alpha \in A) a, b \in X_{\alpha}\) y\(a \preceq_{\alpha} b\).

Demostrar que\(R\) es un orden bien de\(\bigcup_{\alpha \in A} X_{\alpha}\).

EJERCICIO 4.31. Dejar\(X\) ser un conjunto finito y\(f: X \rightarrow X\). Demostrar que\(f\) es una inyección iff\(f\) es una sobreyección.