2: Inducción y Recursión
- Page ID
- 112654
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Si no está familiarizado con el Principio de Inducción Matemática, debe leer el Apéndice B. El principio de inducción matemática establece que Para probar una declaración sobre un entero\(n\), si podemos\(1\). Demostrar la sentencia cuando\(n = b\), para algún entero fijo\(b\), y\(2\). Demostrar que la verdad de la declaración para\(n = k − 1\) implica la verdad de la declaración para\(n = k\) siempre\(k > b\), entonces podemos concluir que la afirmación es verdadera para todos los enteros\(n ≥ b.\)
- 2.1: Algunos ejemplos de introducción matemática
- El principio de inducción matemática establece que para probar una declaración sobre un entero n, si podemos 1) Probar la sentencia cuando n = b, para algún entero fijo b, y 2) Mostrar que la verdad de la sentencia para n = k−1 implica la verdad de la sentencia para n = k siempre que k > b, entonces podemos concluir que la declaración es verdadera para todos los enteros n ≥ b.
- 2.3: Gráfica y Árboles
- En la Sección 1.3.4 se introdujo la idea de una gráfica dirigida. Las gráficas constan de vértices y aristas. Describimos vértices y aristas de la misma manera que describimos puntos y líneas en geometría: en realidad no decimos qué son los vértices y aristas, sino que decimos lo que hacen. Simplemente no tenemos un sistema de axiomas complicado como lo hacemos en geometría. Un gráfico consiste en un conjunto V llamado conjunto de vértices y un conjunto E llamado conjunto de bordes. Cada miembro de V se llama vértice y cada miembro de E se llama borde.
- 2.4: Aplicaciones de la Inducción y Recursión en Combinatoria y Teoría de Gráficas (Ejercicios)
- Esta sección contiene los problemas suplementarios relacionados con los materiales tratados en el Capítulo 2.
Miniaturas: Un dibujo de una gráfica. (Dominio público; AzaToth).