• ↑
  • MAT102 Final Exam Prep

MAT102 Worksheet 8 Review

Q1

• The fibonacci sequence is defined recursive as $f_1=f_2=1$ and $f_n=f_{n-1}+f_{n-2}$ for $n\ge 3$.

A

• Show that $gcd(f_n,f_{n+1})=1$ for all $n\ge 1$.
• Base Case: $n=1,2,3$
  • $gcd(f_1,f_2)=1$
  • $gcd(f_2,f_3)=1$
  • $gcd(f_3,f_4)=$
    • $f_3=2$
    • $f_4=f_3+f_2$
    • $f_4=2+1$
    • $f_4=3$
    • $gcd(f_3,f_4)=1$
  • $gcd(f_3,f_3+f_2)=$
    • $gcd(2,2+1)=1$
• Induction Hypothesis:
  • For some arbitrary $n\ge 3$, $gcd(f_n,f_{n+1})=1$
• Induction Step:
  • So we know that for example: $gcd(a+b,b)=gcd(a,b)$
  • So $gcd(f_n,f_{n+1})=1$ now let's show this can turn into $gcd(f_{n+1},f_{n+2})=1$
  • Notice $f_{n+2}=f_{n+1}+f_n$
  • So we have $gcd(f_{n+1},f_{n+1}+f_n)=1$
  • Notice this matches our example
  • So $gcd(f_n,f_{n+1})=gcd(f_{n+1},f_{n+1}+f_n)$
  • Where $a=f_n,b=f_{n+1}$
  • So we have shown that this is true.

B

• Show that $\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}$
• Base Case: $n=1$
  • $f_1^2=f_1{f}_2$
  • $(1{)}^2=(1)(1)$
  • Done
• Induction Hypothesis:
  • For some arbitrary $n\in \mathbb{N}$ $\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}$
• Induction Step:
  • Let's 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}$
  • Pull out the last term
  • $\sum _{i=1}^n(f_i{)}^2+(f_{n+1}{)}^2=f_{n+1}{f}_{n+2}$
  • $f_n{f}_{n+1}+(f_{n+1}{)}^2=f_{n+1}{f}_{n+2}$ Via IH
  • $f_n{f}_{n+1}+f_{n+1}{f}_{n+1}=f_{n+1}{f}_{n+2}$
  • $f_{n+1}(f_n+f_{n+1})=f_{n+1}{f}_{n+2}$
  • The definition of $f_{n+2}=f_{n+1}+f_n$
  • $f_{n+1}{f}_{n+2}=f_{n+1}{f}_{n+2}$
  • $◻$

C

• Show that $\sum _{i=1}^n{f}_{2i-1}=f_{2n}$
• Base case: $n=1$
  • $f_{2(1)-1}=f_{2(1)}$
  • $f_1=f_2$
  • True
• Induction Hypothesis:
  • For some arbitrary $n\in \mathbb{N}$ $\sum _{i=1}^n{f}_{2i-1}=f_{2n}$
• Induction Step:
  • Let's show that $\sum _{i=1}^n{f}_{2i-1}=f_{2n}⟹\sum _{i=1}^{n+1}{f}_{2i-1}=f_{2n+2}$
  • Notice that $\sum _{i=1}^{n+1}{f}_{2i-1}=\sum _{i=1}^n{f}_{2i-1}+f_{2(n+1)-1}$
  • $\sum _{i=1}^{n+1}{f}_{2i-1}=\sum _{i=1}^n{f}_{2i-1}+f_{2n+1}$
  • $\sum _{i=1}^n{f}_{2i-1}+f_{2n+1}=f_{2n+2}$
  • $f_{2n}+f_{2n+1}=f_{2n+2}$
  • $◻$

Q2

• Given a function $f$, there is an operation we can apply to $f$ called differentiation. The result of differentiating $f$ is a new function $D(f)$. If we differentiate this function again, we get another function which we'll denote as $D^2(f)$. In general, if we apply this operation $n$ times, we get $D^n(f)$. We also know the following facts: If $f$, $g$ are functions, and $c\in \mathbb{R}$, then:
  • P1. $D(fg)=D(f)g+fD(g)$,
  • P2. $D(cf+g)=cD(f)+D(g)$.

A

• If $c_1,\dots ,c_n$ are real numbers and $f_1,\dots ,f_n$ are functions show that:
  • $D\left(\sum _{k=1}^n{c}_k{f}_k\right)=\sum _{k=1}^n{c}_{k}D(f_k)$
  • This is the fact that we can leave out constants that are multiplied with a differentiated function
  • Base Case:
    • $n=1$
    • $D(c_k{f}_k)=c_{k}D(f_k)$
    • Notice this models P2.
    • So this is true.
  • Induction Hypothesis:
    • For some arbitrary $n\in \mathbb{N}$, $D\left(\sum _{k=1}^n{c}_k{f}_k\right)=\sum _{k=1}^n{c}_{k}D(f_k)$
  • Induction Step:
    • Show that $D\left(\sum _{k=1}^n{c}_k{f}_k\right)=\sum _{k=1}^n{c}_{k}D(f_k)⟹D\left(\sum _{k=1}^{n+1}{c}_k{f}_k\right)=\sum _{k=1}^{n+1}{c}_{k}D(f_k)$
    • Notice that $D\left(\sum _{k=1}^{n+1}{c}_k{f}_k\right)=D(\sum _{k=1}^n{c}_k{f}_k+c_{n+1}{f}_{n+1})$
    • $D(\sum _{k=1}^n{c}_k{f}_k+c_{n+1}{f}_{n+1})=\sum _{k=1}^n{c}_{k}D(f_k)+c_{n+1}D(f_{n+1})$
    • $D\left(\sum _{k=1}^n{c}_k{f}_k\right)+D(c_{n+1}{f}_{n+1})=\sum _{k=1}^n{c}_{k}D(f_k)+c_{n+1}D(f_{n+1})$
    • By P2
    • $\sum _{k=1}^n{c}_{k}D(f_k)+c_{n+1}D(f_{n+1})=\sum _{k=1}^n{c}_{k}D(f_k)+c_{n+1}D(f_{n+1})$
    • $◻$

B

• For $n,k\in \mathbb{N}$, define $F(n,k)=\prod _{i=1}^k\frac{n-i+1}{i}$. We'll say that $F(n,0)=1$ for any choice of $n$. Show that if $n,k\ge 1$ then $F(n,k)=F(n-1,k-1)+F(n-1,k)$
• Let's fix $n\in \mathbb{N}$ to be arbitrary.
  • $\prod _{i=1}^k\frac{n-i+1}{i}=\prod _{i=1}^{k-1}\frac{(n-1)-i+1}{i}+\prod _{i=1}^k\frac{(n-1)-i+1}{i}$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=\prod _{i=1}^{k-1}\frac{n-i}{i}+\prod _{i=1}^k\frac{n-i}{i}$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=\prod _{i=1}^{k-1}\frac{n-i}{i}+\prod _{i=1}^{k-1}\frac{n-i}{i}\cdot \frac{n-k}{k}$
  • If $p=\prod _{i=1}^{k-1}\frac{n-i}{i}$
  • Then we have
  • $\prod _{i=1}^k\frac{n-i+1}{i}=p+p\cdot \frac{n-k}{k}$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=p(1+\frac{n-k}{k})$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=p(\frac{k}{k}+\frac{n-k}{k})$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=p\left(\frac{n}{k}\right)$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=\prod _{i=1}^{k-1}\frac{n-i+1}{i}\cdot \left(\frac{n}{k}\right)$
  • The last term of $\prod _{i=1}^k\frac{n-i+1}{i}=\frac{n-k+1}{k}$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=\frac{k(n\cdot k^{-1}-1+k^{-1})}{k}$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=n\cdot k^{-1}-1+k^{-1}$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=\frac{n}{k}-1+\frac{1}{k}$
  • $\prod _{i=1}^k\frac{n-i+1}{i}=\prod _{i=1}^{k-1}\frac{n-i}{i}\frac{n-k+1}{k}$