×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Shlomo Oved

5

0

5

# Discrete Mathematics Week 5 MA-UY 2314

Marketplace > New York University > Mathematics > MA-UY 2314 > Discrete Mathematics Week 5
Shlomo Oved
NYU

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

Discrete Mathematics Week 5
COURSE
Discrete Mathematics
PROF.
Dr Nasir Memon
TYPE
Class Notes
PAGES
5
WORDS
KARMA
25 ?

## Popular in Mathematics

This 5 page Class Notes was uploaded by Shlomo Oved on Sunday October 9, 2016. The Class Notes belongs to MA-UY 2314 at New York University taught by Dr Nasir Memon in Fall 2016. Since its upload, it has received 5 views. For similar materials see Discrete Mathematics in Mathematics at New York University.

×

## Reviews for Discrete Mathematics Week 5

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/09/16
Shlomo  Oved   Discrete  Mathematics  Week  5   10/09/16   10/03/2016  Lecture  (Week  5)   • ???? = 0,1,2,3…  is  the  set  of  natural  numbers.  We  also  have  functions  to   generate  lists  (sets  of  even  numbers  and  odd  numbers  from  N).   • even  ???? = 2???? → 0,2,4,6…   • odd  ???? = 2???? + 1 → 1,3,5,7…   • ???? ∪ ???? = ????,???? ∩ ???? = ∅   • Definition-­‐  A  sequence  is  a  set  of  numbers  written  in  some  particular  order.   Sequences  can  be  finite  and  infinite.     • (Rosen)  Definition-­‐  A  sequence  is  a  function  from  a  subset  of  N  to  a  set  S.  We   use  the  notatnon  a  to  denote  the  image  on  integer  n.  We  call  a  a  term  of  the   sequence.       • An  arithmetic  progression-­‐   • ???? = ????;???? = ???? + ????;  ???? = ???? + ???? = ???? + 2????;…???? = ???? + ???? − 1 ????   ▯ ▯ ▯ ▯ ▯ ▯ ▯ ▯ • ???? = 1 + 2 + 3 + ⋯+ ????   ???? ????▯???? • ???? = ????   • ????▯= ???? +▯???? + ????▯+ ???? + 2???? + ▯+ [???? + ???? − 1 ????] ▯  • ????▯= ???? + ▯ − 1 ???? + ???? + ???? − 2▯???? + ⋯+ [???? ]   ▯ • 2????▯= 2???? + ▯ − 1 ???? + 2???? + ???? − 1 ????▯+ ⋯+ [2???? + ???? − 1 ????]   ▯ • 2????▯= ????[2???? + ▯ − 1 ????]   ???? ????????????▯ ????▯???? ???? • ????????= ????   ▯ ???? • ????????= ▯ ????▯+ ???? +▯???? − 1 ???? = [???? + ???? ???? ???? ????     • A  geometric  progression-­‐   • ???? = ????;???? = ???? ∗ ????;???? = ???? ∗ ???? = ???? ???? …???? ???? ▯ ▯▯▯   ▯ ▯ ▯ ▯ ▯ ▯ ▯ • ????▯= ???? +▯???? ???? ▯ ???? ???? +▯⋯???? ???? ▯ ▯▯▯   • ???????? = ???? ???? + ???? ???? + ⋯???? ???? ▯▯▯ + ???? ????   ▯ ▯ ▯ ▯ ▯ ▯ • ????????▯− ???? =▯−???? + ???? ▯ ▯ • ???? ???? − 1 = ???? (???? − 1)   ▯ ???? ▯ • ????????= ???? ???? ???? ▯????   ????▯????     • The  Fibonacci  Sequence     • ????▯= 1;???? = ▯;???? = ???? ▯ ▯▯▯ + ???? ▯▯▯;   • 1,  1,  2,  3,  5,  8,  13,  21…   • ????▯= ???? +▯???? ???? • ????▯+ ???? =▯???? ▯ • ????▯= ???? −▯???? ▯ • ????▯= ???? −▯???? ▯ • ????▯= ???? −▯???? ▯ • ????▯▯▯ = ???? ▯▯▯ − ???? ▯   • ????▯= ???? ▯▯▯ − ???? ▯▯▯   • ????▯+ ???? +▯⋯+ ????   ▯ Shlomo  Oved   Discrete  Mathematics  Week  5   10/09/16   • ???? ▯ ???? + ▯+ ???? = ???? ▯ ▯▯▯ − 1   • ???? = 1;???? = 1;????????????????????????  ????????????????????????????????????????   ▯ ▯ • ???? ▯ ???? ▯▯▯ + ???? ▯▯▯  ????????????????????????????????????????  ????????????????????????????????     • Sigma  Notation   ▯ • ????▯+ ???? +▯???? + ????▯+ ⋯+ ▯ = ▯ ▯▯▯ ????▯       • ▯ ????^3 = 1 + 2 + 3 + 4 + 5   ▯ ▯▯▯ • ▯▯▯ ???? = ???? + ???? + ???? + ???? + ⋯+ ???? = ????????   • ▯▯▯ ???? ???? = ???? ▯▯▯ ????   ▯ ▯ • ▯▯▯ (????▯+ ????) = ???????? ▯ ▯▯▯ ????   ▯ • ▯▯▯ ▯▯▯???????? = ▯▯▯(???? + 2???? + 3????) = ▯▯▯(6????) = 6 1 + 2 + 3 + 4 = 60       • The  set  of  real  numbers  R  is  linearly  ordered.  That  is  given  ????,???? ∈ ????,????ℎ????????  ???? ≤ ????  ????????  ???? ≤ ????.   • Q  is  linearly  ordered.   • The  integers  in  Z  are  also  linearly  ordered,  but  also  have  a  very  interesting   property  that  to  each  ???? ∈ ????  there  is  a  next  integer  or  a  successor.   • The  existence  of  a  successor  for  each  element  in  Z  is  called  the  Well-­‐Ordering   Principle.   • We  say  that  Z  is  well-­‐ordered  because  ???? ⊂ ????,????  ????????  ???????????????? − ????????????????????????????.   ▯ ▯ ▯ • 0 = 1;11 = 12;121 = 122;   • Q  is  not  well-­‐ordered-­‐>  there  is  no  unique  successor  to  O .     • The  well-­‐ordered  property:   • Definition-­‐  Given  only  element  ???? ∈ ????,  there  is  a  unique  next  element  of   ▯ successor  element  ????  (???? + 1).   • There  is  no  element  in  N  that  ???? = 0.   • The  set  R  is  linearly  ordered  but  no  well-­‐ordered.   • For  ex:   2  ℎ????????  ????????  ????????????????????????????????   • There  should  be  nothing  between  a  member  and  its  successor.     • N  is  well-­‐ordered  and  it  has  two  additional  properties.   • The  Trichotomy  Property-­‐  given  n,  ???? ∈ ????,  then  exactly  one  of  the  following   relationships  holds:   • ???? < ????  ????????  ???? > ????  ????????  ???? = ????   • The  Minimum  Property:  If  A  is  a  well-­‐ordered  set,  then  each  non-­‐empty   subset  of  A  has  a  unique  minimum  element.       ▯ • Given  ???? < ???? ∈ ????,????ℎ????????  ???? ≤ ????   • For  an  integer  n,  let  P(n)  denote  an  assertion.  Suppose  that:   • 1.  (The  basis  step)  P(1)  or  P(0)  is  true,  and   • 2.  (The  induction  step)  for  all  positive  integers  n,  if  P(n)  is  true,  then  P(n+1)   is  true.   • Then  P(n)  holds  for  all  possible  integers  n.   Shlomo  Oved   Discrete  Mathematics  Week  5   10/09/16   ▯ • Prove  by  induction  that  ???? + 2????  is  divisible  by  3  for  every  non-­‐negative   integer  n.   • Solution:  Let  P(n)  be  the  mathematical  statement  (???? + 2????)  is  divisible  by  3.   • Basis  step:  when  n=0,  1  the  statement  is  true.   • P(1)  is  correct.   • Inductive  hypothesis:  Assume  that  P(k)  is  correct  for  some  positive  integer  k.   ▯ ▯ That  means  (???? + 2????)  is  divisible  by  3  and   ???? + 2???? = 3????  for  some  integer   m.       • Inductive  steps:  We  will  now  show  that  P(k+1)  is  correct.  So  we  will  take  the   original  formula  and  replace  the  n  with  (k+1)  to + 2 ???? + 1 ]  1 and  we  will  show  that  this  is  divisible  by  3.  At  some  stage  in  the  proof  we  will   ▯ need  to  use  the  fact  that   ???? + 2???? = 3????,  so  when  we  re-­‐arrange  the  formula   we  will  try  to  get  (???? + 2????)  as  part  of  it.   • ???? + 1 ▯ + 2 ???? + 1 = ???? + 3???? + 3???? + 1 + 2???? + 2   ▯ ▯ ▯ • ???? + 1 + 2 ???? + 1 = ???? + 2???? + 3(???? + ???? + 1)   • ???? + 1 ▯ + 2 ???? + 1 = 3???? + 3(???? + ???? + 1)   • ???? + 1 ▯ + 2 ???? + 1 = 3(???? + ???? + ???? + 1)       • Because  (???? + ???? + ???? + 1)  is  an  integer  we  have  that  + 2 ???? + 1 ]  is   divisible  by  3,  so  P(k+1)  is  correct.  Therefore  by  mathematical  induction  P(n)   is  correct  for  all  non-­‐negative  integers  n.     • Ex:  Prove  by  induction  that  2 > 2????  for  every  positive  integer  n>2.   ▯ • Solution:  Let  P(n)  be  the  mathematical  statement  2 > 2????   • Basis  step:  When  n=3  we  have  2 > 6 = 8 > 6,????????  ???? 3  ????????  ????????????????????????????.   • Induction  Hypothesis:  Assume  that  P(k)  is  correct  for  some  positive  integer   ▯ k.  That  means  that  2 > 2????.   • Inductive  Step:  We  will  now  show  that  P(k+1)  is  correct   • 2 ▯▯▯ = 2 ∗ 2 > 2 ∗ 2????   ▯▯▯ ▯ • 2 = 2 ∗ 2 > 2(???? + 1)   • So  P(k+1)  is  correct.  Therefore  by  mathematical  induction  P(n)  is  correct  for   all  positive  integers  n>2.       • Ex:  Prove  by  induction  that  (11 − 6)  is  divisible  by  5  for  every  positive   integer  n.   ▯ • Solution:  Let  P(n)  be  the  mathematical  statement  (11 − 6)  is  divisible  by  5.     • Basis  step:  When  n=1  we  have  11 − 6 = 5  which  is  divisible  by  5.  So  P(1)  is   correct.   • Induction  hypothesis:  Assume  that  P(k)  is  correct  for  some  positive  k.  That   means  (11 − 6)  is  divisible  by  5  and  so   11 − 6 = 5????  for  some  integer  m.   So  11 = 5???? + 6.   • Inductive  step:  We  will  now  show  that  P(k+1)  is  correct.  Always  keep  in  mind   what  we  are  aiming  for  and  what  we  know  to  be  true.  In  this  case  we  want  to   Shlomo  Oved   Discrete  Mathematics  Week  5   10/09/16   show  (11 ▯▯▯ − 6)  can  be  expressed  as  a  multiple  of  5,  so  we  will  re-­‐arrange  it   into  something  involving  multiples  of  5.  At  some  point  we  will  also  want  to   use  the  assumption  that  (11 = 5???? + 6)   • 11 ▯▯▯ − 6 = 11 ∗ 11 ▯ − 6   ▯▯▯ • 11 ▯▯▯ − 6 = (11 ∗ 5???? + 6 − 6   • 11 − 6 = (11 ∗ 5????) + 66 − 6   • 11 ▯▯▯ − 6 = 5 ∗ 11???? + 60   • 11 ▯▯▯ − 6 = 5(11 ∗ ???? + 12)   ▯▯▯ • As  (11 ∗ ???? + 12)  is  an  integer  we  have  that− 6)  is  divisible  by  5,  so   P(k+1)  is  correct.  Therefore  by  math  induction  P(n)  is  correct  for  all  positive   integers  n.   • The  power  of  mathematical  induction  comes  from  the  fact  that  it  works  for   any  process  defined  for  each  ???? ∈ ????.  The  limits  of  Mathematical  Induction   come  from  the  fact  that  it  only  works  for  processes  defined  for  each  ???? ∈ ????.   • 10/05/16  Lecture  (Week  5)   • 1.  Midterm  Oct  17-­‐  one  cheat  sheet  handwritten  both  sides  8.5x11   • 2.  Hw  1  to  Hw  5   • 3.  Ch  1-­‐  1.7,  1.8   •        Ch  2-­‐  2.1-­‐2.4   •        Ch  3-­‐  3.1-­‐3.3   •        Ch  5-­‐  5.1-­‐5.2   •        Ch  6-­‐  6.1-­‐6.4       • Induction   • To  prove  that  P(n)  is  true  for  all  positive  integers  n,  we  do  this  in  2  steps.   • 1.  Basis  step-­‐  Verify  P(1)  is  true.   • 2.  Induction  Step-­‐  we  show  that  ???? ???? → ????(???? + 1)  is  true  for  all  positive   integers  k.   • Ex:   ▯ ▯▯▯ • 1 + 2 + 3 + ⋯+ ???? =   ▯ ▯▯▯ ▯ • Bases:  ???? 1 = ▯   • Induction  Step:   ▯▯▯ ▯▯▯ • 1 + 2 + 3…???? + ???? + 1 =   ▯     • Greedy  Algorithm  for  Scheduling  talks   • Given   ▯ ,????▯−starting  and  ending  times  for  t▯lk  ???? ,1 ≤ ???? ≤ ????.   • Sort  talks  by  ending  time  so  that  ???? ≤ ???? ≤ ⋯????  and  relabel  them.   ▯ ▯ ▯ •              S=0   •              for  i=1  to  n   •       i                  if  talk  is  compatible  with  already  scheduled  tasks   •             ▯              ???? ≔ ???? ∪ ????????????????   •              return  s   • O(n  log(n))   Shlomo  Oved   Discrete  Mathematics  Week  5   10/09/16   • Proof  of  correctness?  -­‐>  Induction   • P(1)   • Let  n  be  the  number  of  talks  scheduled  by  the  greedy  algorithm   • P(1)   • Basis  step-­‐  Greedy  algorithm  scheduled  just  one  talk   • ????▯,???? ▯   • All  the  other  talks  begin  before  and  end  after.  Everything  conflicts.  All  other   talks  contain ▯  ???? .   • So  greedy  algorithm  has  picked  optimal  schedule  as  only  one  talk  can  be   scheduled     • Induction  Step   • ???? ???? → ???? ???? + 1   • given  some  input  suppose  greedy  algorithm  scheduled  k+1  talks   • ????▯= ???? ,????▯,???? ▯ ???? ,▯ ▯ ▯ …???? ▯▯▯ = (???? ▯▯▯ ,???? ▯▯▯ )   • ????▯= ???? ,????▯,???? ▯ ???? ,▯ ▯ ▯ …???? ▯▯▯ = ???? ▯▯▯ ,???? ▯▯▯  ????????????????  ????ℎ????????  (???? + 1)   • Claim-­‐  I  can  replace ▯  ????  by  ????  to  get  a  new  schedule  that  remains  optimal.   ▯   • Strong  Induction   • Assume  ???? 1 → ????????????????  (Basis  step)   • Induction  step  ???? 1 ,???? 2 ,…???? ???? → ????????  ????????????????   •   •                               •                                                            P(k+1)  is  true

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com