Writing Direct Proofs | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 1.7 Free with a free account

Writing Direct Proofs

Discrete Mathematics · Chapter 1: Logic and Mathematical ProofSection 1.7 · lesson 7 of 879 min · free with a free account

← Laws of Logic and Logical EquivalenceNext lesson: Tautologies and Contradictions →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

From "testing isn't proof" to actually writing one.

  • Describe the structure of a direct proof
  • Prove parity and divisibility claims by unfolding definitions
  • Write a proof another reader can verify line by line
  • Distinguish a proof from checking examples

Transcript

Everything said in the video, section by section (1,276 words). Read along, or search it.

Logic and Mathematical Proof

Writing Direct Proofs

In section one point one, a mathematician refused to accept that ten thousand passing tests prove a sorting algorithm correct. That's easy to agree with. It's much harder to act on, because knowing that testing isn't proof doesn't tell you how to write a proof instead. This section supplies exactly that. The structure, the standard patterns, and the writing conventions of the most fundamental proof method in mathematics, the direct proof.

The Opening Problem

2 Students, One Claim

A discrete mathematics study group is asked to justify a claim. The sum of any two odd integers is even. One student checks a few cases. One plus three is four. Five plus seven is twelve. Nine plus eleven is twenty. And declares the claim proved. A second student writes an argument that starts from the definition of an odd integer, and ends at the definition of an even one, without ever naming a specific number. Both students believe the claim. Only one has actually established it. And a grader who has seen this exact submission many times accepts only the second.

Definition 1.7.1

The Anatomy of a Direct Proof

Most claims worth proving in discrete mathematics are conditional statements. If P, then Q. The most direct route, and the one that gives the method its name, is to assume P is true, and reason forward until Q follows as a necessary consequence. Each step must be justified by an accepted definition, a previously proved result, or a valid algebraic or logical rule. Two features are easy to state and easy to violate. First, the assumption must be about an arbitrary object. Let n be an even integer, not let n be four. A claim about every even integer can't be established by looking at one of them. Second, every later line must be licensed by something already accepted. A step that merely looks plausible is not the same as a step that's justified.

Worked Proof

If n Is Even, Then n Squared Is Even

Here's the template in action. The claim is, if n is an even integer, then n squared is even. Let n be an arbitrary even integer. By the definition of even, there's an integer k with n equal to two k. Square both sides. n squared equals two k, squared, which is four k squared. Factor it as two times two k squared. Since k is an integer, two k squared is an integer too, because the integers are closed under multiplication. Call it m. So n squared equals two m. That's exactly the form the definition of even requires. So n squared is even. Notice the proof never depended on which even integer n was. Substituting two k for n is what makes every later step valid for every even integer at once.

Figure 1.7.1

The Direct-Proof Template

This figure shows the direct-proof template as five stages. Assume the hypothesis, for an arbitrary object. Unfold the relevant definition into an equation. Manipulate it algebraically. Arrive at a statement matching the definition of the conclusion. And conclude, stating what was shown. Every worked proof in this section follows exactly this shape, whatever the specific claim.

Definitions 1.7.2 and 1.7.3

Replace Words With Equations

Early direct proofs mostly fall into a few recognizable patterns. Two of the most common concern parity, meaning evenness and oddness, and divisibility. An integer n is odd if there's an integer k with n equal to two k plus one. And for integers a and b, a divides b if there's an integer k with b equal to a times k. Both patterns rely on the same move. Replace a property named in words with the algebraic equation its definition supplies.

Worked Proof

The Product of 2 Odd Integers Is Odd

The claim is, the product of two odd integers is odd. Let m and n be arbitrary odd integers. By definition, m equals two j plus one, and n equals two k plus one, for some integers j and k. Multiply them. m times n equals four j k, plus two j, plus two k, plus one. Factor a two out of the first three terms. That gives two times the quantity two j k plus j plus k, plus one. Since j and k are integers, that quantity is an integer too, because the integers are closed under multiplication and addition. Call it p. So m times n equals two p plus one, which matches the definition of odd. The product of two odd integers is odd.

Worked Proof

Divisibility Is Transitive

Now a divisibility claim. For integers a, b, and c, if a divides b and b divides c, then a divides c. Let a, b, and c be integers with a dividing b, and b dividing c. By the definition, there's an integer j with b equal to a j. And there's an integer k with c equal to b k. Substitute the first equation into the second. c equals a j, times k, which is a times j k. Since j and k are integers, j k is an integer. Call it m. So c equals a times m, which matches the definition. a divides c. That's the characteristic divisibility move. Substitute one equation into another.

Table 1.7.1

3 Recurring Patterns

This table summarizes the three recurring patterns, by the definition unfolded and the typical algebraic move. For an even-parity claim, unfold n equals two k, then substitute, expand, and factor out a two. For an odd-parity claim, unfold n equals two k plus one, then expand and factor into the form two times something, plus one. And for divisibility, unfold b equals a k, and substitute one equation into another. Every pattern ends the same way. You arrive at exactly the form the conclusion's definition requires.

Writing Conventions

Written So Every Step Can Be Checked

A direct proof is judged not only on whether its algebra is right, but on whether another reader can verify every step without guessing. Three conventions make that possible. First, state the assumption precisely and generally. Let n be an arbitrary even integer commits the proof to every even integer. Naming a specific number commits it to nothing beyond that number. Second, justify every step. Each line should trace to a definition, an accepted algebraic fact, or a proved result. Never to clearly, or obviously. Third, end with an explicit concluding statement, ideally with an end-of-proof marker, so the reader knows exactly where the argument ends, and what it established.

Table 1.7.2 - What a Direct Proof Is Not

Illustration Versus Proof

Checking a handful of numeric cases, however many, is not a direct proof. It's an illustration. Back to the study group. The first student checked specific cases, used no arbitrary representative, and established only the cases checked. Nothing in that argument rules out a counterexample among the infinitely many pairs never tried. The second student's argument worked because it replaced two specific numbers with the general forms, two j plus one, and two k plus one. The same move used in every proof in this section. One more boundary. Section one point five showed a conditional is equivalent to its contrapositive. So a proof could assume not Q, and derive not P. That's a genuinely different technique, proof by contrapositive, taken up later in this chapter. Every proof here reasons forward, from P to Q.

Takeaways

Assume, Unfold, Manipulate, Match

To summarize. A direct proof of if P, then Q, assumes P for an arbitrary object, and derives Q through a chain of justified steps. Parity and divisibility claims share a pattern. Replace a property stated in words with the equation its definition supplies, and manipulate until the target form appears. Checking specific cases, however many, is not a direct proof. And a rigorous proof states its assumption, justifies every step, and concludes explicitly. Here's something to think about. We proved that if n is even, n squared is even. Is the converse, if n squared is even then n is even, automatically true because the original was? And if it happens to be true, does this proof already establish it?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Writing Direct Proofs

What is a direct proof and how is it structured?
A direct proof of "if P, then Q" assumes P for an arbitrary object and reasons forward, one justified step at a time, until Q follows. The usual stages are assume the hypothesis, unfold the relevant definition into an equation, manipulate it algebraically, match the definition of the conclusion, and state what was shown.
How do you prove that the product of two odd integers is odd?
Unfold the definition of odd for each integer, multiply, and factor into the form 2p+1. Let m=2j+1 and n=2k+1 for integers j and k. Then mn=4jk+2j+2k+1=2(2jk+j+k)+1. Since p=2jk+j+k is an integer, mn=2p+1, which is odd.
How do you prove a divisibility statement like "if a divides b and b divides c, then a divides c"?
Unfold the definition of divides for each hypothesis, then substitute one equation into the other. If a divides b and b divides c, then b=aj and c=bk for integers j and k. Substituting gives c=a(jk). Because jk is an integer, a divides c by definition.
Why isn't checking several examples a proof?
Checking examples only establishes the cases you tried, so it is an illustration, not a proof. Testing 1+3, 5+7, and 9+11 cannot rule out a counterexample among the untested pairs. A proof starts from an arbitrary object, such as 2j+1 and 2k+1 for odd integers, so every step holds for all of them at once.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →