eBook - ePub
A Short Course in Discrete Mathematics
Edward A. Bender, S. Gill Williamson
This is a test
Compartir libro
- 256 páginas
- English
- ePUB (apto para móviles)
- Disponible en iOS y Android
eBook - ePub
A Short Course in Discrete Mathematics
Edward A. Bender, S. Gill Williamson
Detalles del libro
Vista previa del libro
Índice
Citas
Información del libro
What sort of mathematics do I need for computer science? In response to this frequently asked question, a pair of professors at the University of California at San Diego created this text. Its sources are two of the university's most basic courses: Discrete Mathematics, and Mathematics for Algorithm and System Analysis. Intended for use by sophomores in the first of a two-quarter sequence, the text assumes some familiarity with calculus. Topics include Boolean functions and computer arithmetic; logic; number theory and cryptography; sets and functions; equivalence and order; and induction, sequences, and series. Multiple choice questions for review appear throughout the text. Original 2005 edition. Notation Index. Subject Index.
Preguntas frecuentes
¿Cómo cancelo mi suscripción?
¿Cómo descargo los libros?
Por el momento, todos nuestros libros ePub adaptables a dispositivos móviles se pueden descargar a través de la aplicación. La mayor parte de nuestros PDF también se puede descargar y ya estamos trabajando para que el resto también sea descargable. Obtén más información aquí.
¿En qué se diferencian los planes de precios?
Ambos planes te permiten acceder por completo a la biblioteca y a todas las funciones de Perlego. Las únicas diferencias son el precio y el período de suscripción: con el plan anual ahorrarás en torno a un 30 % en comparación con 12 meses de un plan mensual.
¿Qué es Perlego?
Somos un servicio de suscripción de libros de texto en línea que te permite acceder a toda una biblioteca en línea por menos de lo que cuesta un libro al mes. Con más de un millón de libros sobre más de 1000 categorías, ¡tenemos todo lo que necesitas! Obtén más información aquí.
¿Perlego ofrece la función de texto a voz?
Busca el símbolo de lectura en voz alta en tu próximo libro para ver si puedes escucharlo. La herramienta de lectura en voz alta lee el texto en voz alta por ti, resaltando el texto a medida que se lee. Puedes pausarla, acelerarla y ralentizarla. Obtén más información aquí.
¿Es A Short Course in Discrete Mathematics un PDF/ePUB en línea?
Sí, puedes acceder a A Short Course in Discrete Mathematics de Edward A. Bender, S. Gill Williamson en formato PDF o ePUB, así como a otros libros populares de Mathematics y Discrete Mathematics. Tenemos más de un millón de libros disponibles en nuestro catálogo para que explores.
Información
Categoría
MathematicsCategoría
Discrete MathematicsUnit IS
Induction, Sequences and Series
Section 1: Induction
Suppose A(n) is an assertion that depends on n. We use induction to prove that A(n) is true when we show that
- it’s true for the smallest value of n and
- if it’s true for everything less than n, then it’s true for n.
In this section, we will review the idea of proof by induction and give some examples. Here is a formal statement of proof by induction:
Theorem 1 (Induction) Let A(m) be an assertion, the nature of which is dependent on the integer m. Suppose that we have proved A(n0) and the statement
“If n > n0 and A(k) is true for all k such that n0 ≤ k < n, then A(n) is true.”
Then A(m) is true for all m ≥ n0.19
Proof: We now prove the theorem. Suppose that A(n) is false for some n ≥ n0. Let m be the least such n. We cannot have m = n0 because one of our hypotheses is that A(n0) is true. On the other hand, since m is as small as possible, A(k) is true for n0 ≤ k < m. By the inductive step, A(m) is also true, a contradiction. Hence our assumption that A(n) is false for some n is itself false; in other words, A(n) is never false. This completes the proof.
Definition 1 (Induction terminology) “A(k) is true for all k such that n0 ≤ k < n” is called the induction assumption or induction hypothesis and proving that this implies A(n) is called the inductive step. A(n0) is called the base case or simplest case.
Example 1 (Every integer is a product of primes) A positive integer n > 1 is called a prime if its only divisors are 1 and n. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23. In another unit, we proved that every integer n > 1 is a product of primes. We now redo the proof, being careful with the induction.
We adopt the terminology that a single prime p is a product of one prime, itself. We shall prove A(n):
“Every integer n ≥ 2 is a product of primes.”
Our proof that A(n) is true for all n ≥ 2 will be by induction. We start with n0 = 2, which is a prime and hence a product of primes. The induc...