Discrete Mathematics Problems Worth Solving, Questions and Answers
- Prove that the fourth power of an odd integer is expressible in the form 16n + 1 for n ∈ Z.
- Define an by a0 = 1, a1 = 2, a2 = 4 and an+2 = an+1 + an + an−1, for n ≥ 1. Show that an ≤ 2n for all n ∈ N.
- If Fn is the nth Fibonacci number, prove that Fn+1Fn−1 − F2n = (−1)n.
- Let a and n be positive integers with a > 1. Prove that, if a^n + 1 is prime, then a is even and n is a power of 2.
- Show that if all three of p, p + 2 and p + 4 are prime, then p = 3.
- Use the Euclidean algorithm to compute (2059, 2581) and to express this quantity as a linear combination of 2059 and 2581.
- Show that every nonzero integer can be uniquely expressed as ak3^k + ak−13^(k−1) + · · · + a13 + a0 where ai ∈ {−1, 0, 1} and ak ≠ 0.
- Prove that the product of any two integers of the form 6k + 1 is of that same form.
- Prove that any prime p > 3 is either of the form 6k + 1 or of the form 6k + 5 for some integer k.
- Prove that there are infinitely many primes of the form 6k + 5. That is, consider the primes which has a remainder 5 when divided by 6. Prove that there are infinitely many such primes.
- Prove that if k and ℓ are posetive integers then k^2 − ℓ^2 can never be equal to 2.
- If a is an odd integer prove that a^2 − 1 is always divisible by 8.
- Show that for any positive number a and b, (a + b)/2 ≥ √ab
- Let x be an integer. Prove that if x^2 − 6x + 5 is even then x must be odd.
- Show that a^2 + a^4 ≡ 0(mod 5) if a ≡ 2(mod 5) or a ≡ 3(mod 5) or if 5 divides a.
- Show that if a, b, c, and d are integers such that a|c and b|d, then ab|cd.
- Prove that if n is an odd positive integer, then n^2 ≡ 1 (mod 8).
- Prove the logical equivalence of the following statements, ~(p V ~q) V (~p ^ ~q) ≡ ~p
- Determine which of the following pair of statement are logically equivalent: (r V p) ^ ( ( ~r V (p^q) ) ^ (r V q) ) and p ^ q
- Write truth table for the statement forms: ~(p ^ q) V (p V q)
- Construct the truth table for the statements: (pVq) V (~p^q) → q
- Write each of the following three statements in the symbolic form and determine which pairs are logically equivalent: a) If it walks like a duck and it talks like a duck, then it is a duck. b) Either it does not walk like a duck or it…
- Rewrite the statement in the if-then form: A necessary condition for this computer program to be correct is that it does not produce error messages during translation:
- Use symbols to write the logical form of each argument. If the rule is valid then identify the rule of inference that guarantees its validity, otherwise state whether converse or inverse error is made.
- Use truth tables to show that the following forms of argument are invalid:p → q, ~p, hence, ~q (inverse error)
- Use truth tables to determine if the argument forms are valid: p → r q → r hence, p V q → r
- Use inference rules to deduce the following conclusions from the following sets of premises: a) Premises: p ∨ q q → r, p ∧ s → t, ¬r, ¬q → u ∧ s Conclusion: t b) Premises: (p ∧ t) → (r ∨ s), q → (u ∧ t), u → p, ¬s Co…
- Construct a truth table for each of these compound propositions: i) (p ⇔ q) ⇔ (r ⇔ s) ii) (p ⨁ q) ∨ (p ⨁ ¬q)
- Compute the value of the double summation: ∑i ^ 4 = 1 ∑j=i ^4 (3i + j)
- Prove that if x^3 is irrational, then x is irrational
- Show that these compound propositions are tautologies: (1) (¬q ∧ (p → q)) → ¬p (2) ((p ∨ q) ∧ ¬p) → q