MAT102 Lecture 15

• How to Do Re-Indexing
• Collapsing Sigma Notations:
  • Just do rie indexing to change the bounds, then collapse them.
• Harmonic Series Diverges
  • Proof from exercise 3 mathmatize
  • $\sum _{i=i}^{2^n}\frac{1}{i}\ge 1+\frac{n}{2}$
  • Hint group things into powers of 2

• 1
  • a)
    • Show that $gcd(f_n,f_{n+1})=1$ for all $n\ge 1$.
    • We know that $gcd(a+b,b)=gcd(a,b)$
    • $P(n)=gcd(f_n,f_{n+1})=1$
    • Let's prove that $P(1)$ is true:
      • $gcd(f_1,f_2)=1$
      • Defs:
        • $f_1=1$
        • $f_2=1$
      • $gcd(1,1)=1$
      • So this is true
    • Let's prove that $P(n)⟹P(n+1)$
      • If $gcd(f_n,f_{n+1})=1$ then $gcd(f_{(n+1)},f_{(n+1)+1})=1$ or $gcd(f_{n+1},f_{n+2})=1$
      • $gcd(f_{n+1},f_{n+2})=1$
      • $f_{n+2}=f_{n+1}+f_n$
      • $gcd(f_{n+1},f_{n+1}+f_n)=1$
      • Since $gcd(a+b,b)=gcd(a,b)$
      • If $a=f_n$ and $b=f_{n+1}$
      • Then we model what's true, so then $gcd(f_{n+1},f_{n+2})=1$
  • b)
    • Show that $\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}$
    • $P(n)=\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}$
    • Base Case:
      • $P(1)=\sum _{i=1}^1{f}_1^2=f_1{f}_2$
      • $P(1)=\sum _{i=1}^1{f}_1^2=1$
      • $P(1)=\sum _{i=1}^1{1}^2=1$
      • $P(1)=\sum _{i=1}^{1}1=1$
      • $P(1)=1=1$
    • Induction Hypothesis:
      • Assume $P(n)$ is true, then prove $P(n+1)$
      • $P(n)=\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}$
      • $P(n+1)=\sum _{i=1}^{n+1}{f}_i^2=f_{n+1}{f}_{n+2}$
      • Let $k=i-1$
      • $k=(n+1)-1$
      • $k=n$
  • Solutions:
    • a)
      • Base Case
        • $n=1$
        • $gcd(f_1,f_2)$
        • $gcd(1,1)=1$
        • Done
      • Induction Hypothesis
        • Suppose that the $gcd(f_n,f_{n+1})=1$ for some $n$.
        • $gcd(f_{n+1},f_{n+2})$
        • We know that $f_{n+2}=f_{n+1}+f_n$
        • $gcd(f_{n+1},f_{n+1}+f_n)=gcd(f_n,f_{n+1})=1$
    • b)
      • Base Case
        • $n=1$
        • $\sum _{i=1}^1{f}_i^2=f_1^2=1$
          • True
      • Induction Hypothesis
        • Suppose the $\sum _{i=1}^n{f}_i^2=f_{n+1}{f}_n$ for some $n$
      • Induction Step
        • $\sum _{i=1}^{n+1}{f}_i^2=f_{n+1}^2+\sum _{i=1}^n{f}_i^2$
        • So we pull the $n+1$ term of the sum out.
        • $f_{n+1}^2+f_{n+1}{f}_n=f_{n+1}(f_{n+1}+f_n)=f_{n+1}{f}_{n+2}$
    • c)
      • Base Case
        • $n=1$
        • $LHS=\sum _{i=1}^1{f}_{2i-1}=f_{i=1}$
        • $RHS=f_2=1$
      • Induction Hypothesis
        • Suppose that ${}^{†}$ is true for some $n$
      • Induction Step
        • Pull out the $n+1$ term and simplify.