4.3 Direct Proof

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-11-06 Teacher: Prof. Musacchio

Direct Proof

Introduction

Example 1

• Proposition: If $x$ is odd, then $x^2$ is odd.
  • Proof. Suppose $x$ is odd
  • Then $x=2a+1$ for some $a\in \mathbb{Z}$, by definition of an odd number
  • Thus $x^2=(2a+1{)}^2=4a^2+4a+1=2(2a^2+2a)+1$.
  • So $x^2=2b+1$ where $b$ is the integer $b=2a^2+2a$
  • Thus $x^2=2b+1$ for an integer $b$.

Example 2

• Proposition: Let $a$, $b$ and $c$ be integers. If $a|b$ and $b|c$, then $a|c$.
  • Proof. Suppose $a|b$ and $b|c$.
  • By Definition 4.4, we know $a|b$ means $b=ad$ for some $d\in \mathbb{Z}$.
  • Likewise, $b|c$ means $c=be$ for some $e\in \mathbb{Z}$.
  • Thus $c=be=(ad)e=a(de)$, so $c=ax$ for the integer $x=de$.
  • Therefore $a|c$.