CMSC 27100 — Problem Set 4

Instructions

This problem set is due on Friday November 1, 2019 at 23:59. Solutions to Problems should be submitted on Gradescope and will be graded. Solutions to Exercises will not be graded and you should not submit them, although we will be happy to discuss them with you.

Problems

  1. Prove that if $p$ is prime, then $a^p = a \pmod p$ for all $a \in \mathbb Z$.
  2. Solve the congruence $x^{13} + 7x + 5 = 0 \pmod{91}$.
  3. Find an expression for $\sum_{i=0}^n i \cdot i!$ and prove that it is correct.
  4. Let $f_n$ denote the $n$th Fibonacci number. Prove that for all $n \geq 1$, $\gcd(f_n, f_{n-1}) = 1$.
  5. The Fibonacci words over the alphabet $\{0,1\}$ are defined recursively by For example, the first few Fibonacci words are \begin{align*} F_0 &= 0 \\ F_1 &= 01 \\ F_2 &= 010 \\ F_3 &= 01001 \\ F_4 &= 01001010 \\ F_5 &= 0100101001001 \\ F_6 &= 010010100100101001010 \end{align*} Prove that for all $n \in \mathbb N$, $F_n$ does not contain the substring $11$.

Exercises

  1. Rosen 5.1, Exercises 5-8
  2. Rosen 5.1, Exercises 20-21
  3. Rosen 5.1, Exercises 35-37
  4. Rosen 5.2, Exercises 7,9
  5. Rosen 5.2, Exercises 42
  6. Rosen 5.3, Exercises 14-16
  7. Rosen 5.3, Exercises 35, 36
  8. Rosen 5.3, Exercises 41, 42
  9. Let $F_n$ denote the $n$th Fibonacci word and let $f_n$ denote the $n$th Fibonacci number.
    1. Show that for all $n \in \mathbb N$, the number of $1$s in $F_n$ is $f_{n}$.
    2. Show that for all $n \in \mathbb N$, the number of $0$s in $F_n$ is $f_{n+1}$.
    3. Show that for all $n \in \mathbb N$, $|F_n| = f_{n+2}$.
    4. Show that for all $n \in \mathbb N$, $F_n$ does not contain the substring $000$.