Assignment 4

In addition to correct answers, please:

  • Show how you derived your answer.
  • Make all proofs, and longer-answer questions, beautifully organized and easy to read. This includes perfect spelling and grammar.

Please see Canvas for instructions on how and when to submit this assignment.

Question 1

Use mathematical induction to prove that this equation is true for all integers \(n > 0\):

\[\sum_{j=1}^{n} j\cdot j! = (n+1)! - 1\]

Question 2

Use mathematical induction to prove that if \(n\) is an integer bigger than 3, then \(n!\) is bigger than \(2^{n}\).

Question 3

Suppose \(n\) is a positive integer, and \(F_n\) is the nth Fibonacci number. Prove that this equation holds:

\[F_0 + F_1 + F_2 + \ldots + F_n = \sum_{i=0}^{n} F_i = F_{n+2} - 1\]

Question 4

Give a recursive definition (no proof is needed) for the set of all:

  1. positive even integers
  2. nonnegative even integers

Question 5

Suppose \(a, m, n \in \mathbb{Z}\), and \(a \neq 0\). Prove that \((a|n \lor a|m) \Rightarrow a|(mn)\).

Question 6

Prove that if \(n\) is an odd positive integer, then \(n^{2}-1\) is a multiple of 8.

Question 7

  1. Consider the equation \(15a + 9b = n\), where \(a,b \in \mathbb{Z}\) and \(n \in \mathbb{Z}^{+}\). Find values for \(a\), \(b\), and \(n\) that satisfy the equation, and also \(n\) is as small as possible.
  2. Re-do a) using the equation \(51a + 52b = n\).
  3. Prove that there are no values for \(a,b \in \mathbb{Z}\) that satisfy the equation \(70a + 1001b = 5000\).

Question 8

Prove that a positive integer \(n\) is a perfect square if, and only if, \(n\) has an odd number of positive divisors.

Question 9

Suppose two teams are playing a Dota 2 match consisting of, at most, 5 games. The winner of the match is the first team to win 3 games. Draw a tree diagram showing all the ways the match can be decided.