MAT102 Lecture 20B

10InductionIExercises_Students.pdf

• $f_n$ is the fibonacci sequence
  • $f_0=0$
  • $f_1=1$
  • $f_2=1$
  • $f_n=f_{n-1}+f_{n-2}$ for $n\ge 2$
  • $\{0,1,1,2,3,5,8,13,21,34,55,89,\dots \}$
  • Prove that $gcd(f_n,f_{n+1})=1$
    • Base Cases:
      • $n=1$
        • $gcd(f_1,f_2)=gcd(1,1)=1$
      • $n=2$
        • $gcd(f_2,f_3)=1$
        • $gcd(1,1)=1$
      • $n=3$
        • $gcd(f_3,f_4)=1$
        • $gcd(1,2)=1$
      • $n=4$
        • $gcd(f_4,f_5)=1$
        • $gcd(2,3)=1$
    • Induction Hypothesis:
      • For an arbitrary $n$
      • $gcd(f_n,f_{n+1})=1$
    • Induction Step:
      • Want to show that $gcd(f_n,f_{n+1})=1⟹gcd(f_{n+1},f_{n+2})=1$
      • See that we can break the $f_{n+2}$ term into something which appears in our assumed hypothesis.
        • $gcd(f_{n+1},f_{n+2})=1$
        • $gcd(f_{n+1},f_n+f_{n+1})=1$
      • Lemma:
        • $gcd(a,a+b)=1⟹gcd(a,b)=1$
        • $1\mid a$
        • $1\mid a+b$
        • Since $1\mid a$, and $1\mid a+b$
        • $1k=a$
        • $1\ell =a+b$
        • $\ell =k+b$
        • $1(\ell -k)=b$
        • $l-k\in \mathbb{Z}$
        • So let $j=\ell -k$
        • $1j=b$
        • Which proves that $1\mid b$ meaning $gcd(a,b)=1$.
      • By the lemma
        • Let $a=f_n$ and $b=f_{n+1}$
        • $gcd(a,b)=1⟹gcd(a,a+b)=1$
        • So this is true
    • Solution:
      • Claim: $\mathrm{\forall }n\in {\mathbb{Z}}^{+},gcd(f_n,f_{n+1})=1$
      • Proof: We will proceed by induction
      • Base Case:
        • $n=1$
        • $gcd(f_1,f_2)=gcd(1,1)=1$
      • Induction Hypothesis:
        • Assume for some $k$ that $gcd(f_{k+1},f_k)=1$
      • Induction Step:
        • We want to show that $gcd(f_{k+2},f_{k+1})=1$
        • See that $gcd(f_{k+2},f_{k+1})=gcd(\underset{a}{\underbrace{f_k}}+\underset{b}{\underbrace{f_{k+1}}},\underset{b}{\underbrace{f_{k+1}}})$
        • This is $=gcd(f_k,f_{k+1})=1$
        • Done
  • $\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}$
    • Base Case:
      • $n=1$
        • $\sum _{i=1}^1{f}_i^2$
          • $=f_1^2$
          • $=1$
        • $f_1{f}_2$
          • $(1)(1)=1$
      • $n=2$
        • $\sum _{i=1}^2{f}_i^2$
          • $=f_1^2+f_2^2$
          • $=1+1=2$
        • $f_2{f}_3$
          • $1(2)=2$
      • $n=3$
        • $\sum _{i=1}^3{f}_i^2$
          • $=f_1^2+f_2^2+f_3^2$
          • $=1^2+1^2+2^2=6$
        • $f_3{f}_4$
          • $(2)(3)=6$
    • Induction Hypothesis:
      • For arbitrary $n$ assume that $\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}$
    • Induction Step:
      • Want to show that $\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}⟹\sum _{i=1}^{n+1}{f}_i^2=f_{n+1}{f}_{n+2}$
      • $\sum _{i=1}^{n+1}{f}_i^2=f_{n+1}{f}_{n+2}⟹\sum _{i=1}^n{f}_i^2+f_i^2=f_{n+1}{f}_{n+2}$
      • By IH $f_n{f}_{n+1}+f_i^2=f_{n+1}{f}_{n+2}$
      • See that $i$ here is $n+1$
      • $\underset{f_{n+2}}{\underbrace{f_n{f}_{n+1}}}+(f_{n+1}{)}^2=f_{n+1}{f}_{n+2}$
      • $f_{n+1}(f_n+f_{n+1})=f_{n+1}{f}_{n+2}$
      • $f_{n+1}{f}_{n+2}=f_{n+1}{f}_{n+2}$
    • Solution:
      • Claim: $\mathrm{\forall }n\in {\mathbb{Z}}^{+},\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}$
      • Proof: We will proceed by induction
      • Base Case:
        • $n=1$
        • LHS
          • $f_1^2=1$
        • RHS
          • $f_1{f}_2=(1)(1)=1$
      • Induction Hypothesis:
        • Assume for some $k$ that $\sum _{i=1}^k{f}_i^2=f_k{f}_{k+1}$
      • Induction Step:
        • Want to show $\sum _{i=1}^{k+1}{f}_i^2=f_{k+1}{f}_{k+2}$
        • Indeed, $\sum _{i=1}^{k+1}{f}_i^2=\sum _{i=1}^k{f}_i^2+f_{k+1}^2$
        • By IH: $f_k{f}_{k+1}+f_{k+1}^2$
        • $f_{k+1}(\underset{f_{k+2}}{\underbrace{f_k+f_{k+1}}})$
        • $f_{k+1}{f}_{k+2}$
        • Done
  • $\sum _{i=1}^n{f}_{2i-1}=f_{2n}$
    • Base Case:
      • $n=1$
        • $\sum _{i=1}^1{f}_{2i-1}$
          • $f_1=1$
        • $f_{2(1)}=1$
      • $n=2$
        • $\sum _{i=1}^2{f}_{2i-1}$
          • $=f_1+f_3$
          • $=1+2=3$
        • $f_{2(2)}=3$
    • Induction Hypothesis:
      • Assume for some $k$ that $\sum _{i=1}^k{f}_{2i-1}=f_{2k}$
    • Induction Step:
      • Want to show that $\sum _{i=1}^{k+1}{f}_{2i-1}=f_{2k+2}$
      • $\sum _{i=1}^{k+1}{f}_{2i-1}=\sum _{i=1}^k{f}_{2i-1}+f_{2(k+1)-1}$
      • $\sum _{i=1}^k{f}_{2i-1}+f_{2k+1}$
      • By IH: $\underset{f_{2k+2}}{\underbrace{f_{2k}+f_{2k+1}}}$
      • Done
• Consider $H$ the set of formal strings defined as:
  • All strings will only consist of $\{\text{M},\text{I},\text{U}\}$
  • Basis: $\text{MI}\in H$
  • $C_1$: If $\text{M}x\in H$ then $\text{M}xx\in H$
    • You can double the last string after $\text{M}$
  • $C_2:$ If $x\text{I}\in H$ then $x\text{IU}\in H$
    • You can add a $\text{U}$ to any string ending with $\text{I}$
  • $C_3:$ If $x\text{UU}y\in H$ then $xy\in H$
    • Wherever there are two U as $\text{UU}$, you can delete it.
  • $C_4:$ If $x\text{III}y\in H$ then $x\text{U}y\in H$
    • Wherever there are three I as $\text{III}$ you can replace it with a $\text{U}$
  • Try to determine whether the following strings are in $H:\{\text{MUI},\text{MIU},\text{MU}\}$
    • $\text{MUI}$
      • Basis: $\text{MI}$
      • Apply $C_1:\text{MII}$
      • Apply $C_1:\text{MIIII}$
      • Apply $C_3:\text{MUI}$
    • $\text{MIU}$
      • Basis: $\text{MI}$
      • Apply $C_2:\text{MIU}$
    • $\text{MU}$
      • By question 3, we need to show nothing can produce this
  • For an element $x\in H$, define $f(x)$ to be the number of $\text{I}$'s in $x$. Prove for all $x\in H,3\nmid f(x)$
    • Let's list constructors dealing with $\text{I}$
      • $C_1$ can double the amount of $\text{I}$'s. We start with basis $\text{MI}$, and we get $\text{MII},\text{MIIII},\text{MIIIIIIII},\dots$
        • Defined as $f\left(x\right)=2^n,3\nmid f(n)$
        • Base Case:
          • $f(\text{MI})=1$
            • $3\nmid 1$
          • $f(\text{MII})=2$
            • $3\nmid 2$
          • $f(\text{MIIII})=4$
            • $3\nmid 4$
        • Induction Hypothesis:
          • Assume for some $k$ that $3\nmid f(k)$
        • Induction Step:
          • $C_1:$ we double the last string
            • $f(k)=\ell$
            • $3\nmid f(C_1(k))$
            • $3\nmid 2\ell$
            • Lemma:
              • $3\nmid 2^n$ for any $n$
              • Base Case:
                • $n=0$
                • $3\nmid 1$
              • Induction Hypothesis:
                • Assume for some $k_0$ that $3\nmid 2^{k_0}$
              • Induction Step:
                • Want to show that $3\nmid 2^{k_0+1}$
                • $3\nmid 2^{k_0}$
                • $2^{k_0}\equiv 1(\mathrm{mod}3)$
                • $2^{k_0}\equiv 2(\mathrm{mod}3)$
                • $2^{k_0+1}\equiv 2(\mathrm{mod}3)$
                • $2^{k_0+1}\equiv 2\cdot 2(\mathrm{mod}3)=2^{k_0}+1\equiv 1(\mathrm{mod}3)$
                • The only way we get $0$ is if $3\mid 2^{k_0}$, but we assume it doesn't so we've shown it won't divide it for all $n$.
            • By the lemma, since $3\nmid f(x)$ the basis, then any multiple in the form $2^n$ won't be divided either.
          • $C_2:$ doesn't change the number of $\text{I}$'s, so nothing needs to be proven.
          • $C_3:$ doesn't change the number of $\text{I}$'s
          • $C_4:$ Just removes $3$ instances of $\text{I}$'s, since we've proven that $3\nmid f(x)$ for any multiple in the form $2^n$ it won't work at all.
            • Reducing a number not resulting in $x\equiv 0(\mathrm{mod}3)$ will not result in something $\equiv 0(\mathrm{mod}3)$
    • Solutions:
      • Base Case: $f(\text{MI})=1$ and $3\nmid 1$
      • Induction Hypothesis:
        • Suppose $s\in H$ and $3\nmid f(s)$
      • Induction Step:
        • Let $C_i$ for $i=1,2,3,4$ denote the constructors.
        • See that $f(C_2(s))=f(C_3(s))=f(s)$, it doesn't change the number of $\text{I}$'s
          • If $3\nmid f(s)$, then $3\nmid f(C_2(s))$ and $3\nmid f(C_3(s))$
        • $C_1$
          • Note that $f(C_1(s))=2f(s)$
          • You double the number of $\text{I}$'s
          • If $f(s)\equiv 1(\mathrm{mod}3)$, then $f(C_1(s))\equiv 2(\mathrm{mod}3)$
          • If $f(s)\equiv 2(\mathrm{mod}3)$, then $f(C_1(s))\equiv 1(\mathrm{mod}3)$
          • Neither of these are divisible by $0$.
          • So then $f(C_1(s))\not\equiv 0(\mathrm{mod}3)$
        • $C_4$
          • Note that $f(C_4(s))=f(s)-3$
          • Claim: If $3\nmid k$ then $3\nmid k-3$ #tk exercise
          • Therefore, $3\nmid f(C_4(s))$
  • Show that $\text{MU}\notin H$
    • #tk
• Show that for all $n>1$ we have that $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}$
  • Base Case:
    • $n=2$
      • $\frac{1}{1}+\frac{1}{2^2}\ge \frac{3(2)}{2(2)+1}$
      • $\frac{1}{1}+\frac{1}{4}\ge \frac{3(2)}{2(2)+1}$
      • $\frac{4}{4}+\frac{1}{4}\ge \frac{6}{5}$
      • $\frac{5}{4}\ge \frac{6}{5}$
      • $25\ge 24$
  • Induction Hypothesis:
    • Assume for some $j$ that $\sum _{k=1}^j\frac{1}{k^2}>\frac{3j}{2j+1}$