{"id":168719,"date":"2023-02-08T16:14:40","date_gmt":"2023-02-08T22:14:40","guid":{"rendered":"https:\/\/www.mometrix.com\/academy\/?page_id=168719"},"modified":"2025-12-11T12:05:08","modified_gmt":"2025-12-11T18:05:08","slug":"introduction-to-proofs","status":"publish","type":"page","link":"https:\/\/www.mometrix.com\/academy\/introduction-to-proofs\/","title":{"rendered":"Introduction to Proofs"},"content":{"rendered":"<h1>Introduction to Proofs<\/h1>\n\n\t\t\t<div id=\"mmDeferVideoEncompass_hOVWKKp6sZo\" style=\"position: relative;\">\n\t\t\t<picture>\n\t\t\t\t<source srcset=\"https:\/\/www.mometrix.com\/academy\/wp-content\/uploads\/2023\/01\/circle-play-duotone.webp\" type=\"image\/webp\">\n\t\t\t\t<source srcset=\"https:\/\/www.mometrix.com\/academy\/wp-content\/uploads\/2023\/01\/circle-play-duotone.png\" type=\"image\/jpeg\"> \n\t\t\t\t<img fetchpriority=\"high\" decoding=\"async\" loading=\"eager\" id=\"videoThumbnailImage_hOVWKKp6sZo\" data-source-videoID=\"hOVWKKp6sZo\" src=\"https:\/\/www.mometrix.com\/academy\/wp-content\/uploads\/2023\/01\/circle-play-duotone.png\" alt=\"Introduction to Proofs Video\" height=\"464\" width=\"825\" class=\"size-full\" data-matomo-title = \"Introduction to Proofs\">\n\t\t\t<\/picture>\n\t\t\t<\/div>\n\t\t\t<style>img#videoThumbnailImage_hOVWKKp6sZo:hover {cursor:pointer;} img#videoThumbnailImage_hOVWKKp6sZo {background-size:contain;background-image:url(\"https:\/\/www.mometrix.com\/academy\/wp-content\/uploads\/2023\/02\/1797-thumb-final-4.webp\");}<\/style>\n\t\t\t<script defer>\n\t\t\t  jQuery(\"img#videoThumbnailImage_hOVWKKp6sZo\").click(function() {\n\t\t\t\tlet videoId = jQuery(this).attr(\"data-source-videoID\");\n\t\t\t\tlet helpTag = '<div id=\"mmDeferVideoYTMessage_hOVWKKp6sZo\" style=\"display: none;position: absolute;top: -24px;width: 100%;text-align: center;\"><span style=\"font-style: italic;font-size: small;border-top: 1px solid #fc0;\">Having trouble? <a href=\"https:\/\/www.youtube.com\/watch?v='+videoId+'\" target=\"_blank\">Click here to watch on YouTube.<\/a><\/span><\/div>';\n\t\t\t\tlet tag = document.createElement(\"iframe\");\n\t\t\t\ttag.id = \"yt\" + videoId;\n\t\t\t\ttag.src = \"https:\/\/www.youtube-nocookie.com\/embed\/\" + videoId + \"?autoplay=1&controls=1&wmode=opaque&rel=0&egm=0&iv_load_policy=3&hd=0&enablejsapi=1\";\n\t\t\t\ttag.frameborder = 0;\n\t\t\t\ttag.allow = \"autoplay; fullscreen\";\n\t\t\t\ttag.width = this.width;\n\t\t\t\ttag.height = this.height;\n\t\t\t\ttag.setAttribute(\"data-matomo-title\",\"Introduction to Proofs\");\n\t\t\t\tjQuery(\"div#mmDeferVideoEncompass_hOVWKKp6sZo\").html(tag);\n\t\t\t\tjQuery(\"div#mmDeferVideoEncompass_hOVWKKp6sZo\").prepend(helpTag);\n\t\t\t\tsetTimeout(function(){jQuery(\"div#mmDeferVideoYTMessage_hOVWKKp6sZo\").css(\"display\", \"block\");}, 2000);\n\t\t\t  });\n\t\t\t  \n\t\t\t<\/script>\n\t\t\n<div class=\"accordion\"><input id=\"transcript\" type=\"checkbox\" class=\"spoiler_button\" \/><label for=\"transcript\">Transcript<\/label>\n<div class=\"spoiler\" id=\"transcript-spoiler\">\n<p>In this video, we are going to discuss <strong>mathematical proofs<\/strong>, different methods of proving things, and why proofs are useful.<\/p>\n<p>In mathematics, a <strong>proof<\/strong> is a type of logical exercise in which someone pieces together known information to form a conclusion that was previously unknown. Proofs are typically written as a series of logical statements that flow from one to another until the conclusion is reached.<\/p>\n<p>For example, consider the following statement: \u201cIf \\(x\\) is an odd integer, then \\(3x+1\\) must be an even integer.\u201d How can we know that this statement is true? We can validate this claim with a proof. Let\u2019s write one now. Start by writing what we want to show; this way, we can keep in mind exactly where we are trying to go with the proof.<\/p>\n<div class=\"examplesentence\">CLAIM: If \\(x\\) is an odd integer, then \\(3x+1\\) must be an even integer.<\/div>\n<p>\n&nbsp;<\/p>\n<p>Let\u2019s write the first line of the formal proof. The first line is typically used to set up the elements of the problem, which are given in the claim. In this example, we are going to go ahead and establish that \\(x\\) is going to be an odd integer. This statement is usually called the <strong>hypothesis<\/strong>.<\/p>\n<div class=\"examplesentence\">Let \\(x\\) be an odd integer.<\/div>\n<p>\n&nbsp;<\/p>\n<p>Now that we\u2019ve set that up, the next line of the proof needs to be some statement which logically follows as a direct consequence of the first. Odd integers can be expressed in the form \\(2k+1\\), where \\(k\\) is any integer, let\u2019s now write that \\(x\\) is equal to \\(2k+1\\).<\/p>\n<div class=\"examplesentence\">By definition of odd numbers, \\(x=2k+1\\), for some integer \\(k\\).<\/div>\n<p>\n&nbsp;<\/p>\n<p>Let\u2019s see how this changes the expression \\(3x+1\\). When we substitute \\(x=2k+1\\), into the expression \\(3x+1\\), we get \\(3x+1=32(k+1)+1\\).<\/p>\n<div class=\"examplesentence\">So \\(3x+1=3(2k+1)+1\\).<\/div>\n<p>\n&nbsp;<\/p>\n<p>From here, simplify.<\/p>\n<div class=\"examplesentence\">Then \\(3x+1 = 6k+3+1\\).<br \/>\n&nbsp;<br \/>\nThis becomes \\(3x+1=6k+4\\).<\/div>\n<p>\n&nbsp;<\/p>\n<p>Do you remember how even numbers are defined in math? We say that a number is even if it can be represented in the form \\(2k\\), where \\(k\\) is some integer. If we factor out a 2 from \\(6k+4\\), we then end up with \\(2(3k+2)\\). <\/p>\n<div class=\"examplesentence\">\\(6k+4=2(3k+2)\\)<\/div>\n<p>\n&nbsp;<\/p>\n<p>Because 3, \\(k\\), and 2 are all integers, \\(3k+2\\) is also some integer. This all implies that because \\(3k+2\\) is an integer, multiplying it by 2 results in an even integer.<\/p>\n<div class=\"examplesentence\">Since even numbers can be written as \\(2k\\), where \\(k\\) is an integer, and since \\(3k+2\\) is an integer, then \\(2(3k+2)\\) is an even integer.<\/p>\n<p>And because \\(2(3k+2)=3x+1\\), we know that \\(3x+1\\) is an even integer.<\/p>\n<\/div>\n<p>\n&nbsp;<\/p>\n<p>To signal that we have reached the end of the proof, we can draw a small square after the final statement.<\/p>\n<p>This is one example of what a proof may look like, and this particular example is called a <strong>direct proof<\/strong>. Direct proofs start with some known information, and through a series of logical steps, transform the known information into a statement which verifies the claim.<\/p>\n<p>One of the other types of proofs in math is the <strong>indirect proof<\/strong>, in which you verify the claim by showing that all of its alternatives cannot be true. This is like a process of elimination.<\/p>\n<p>Sometimes in math, though, direct proofs and indirect proofs are not the most efficient types of proof. For example, consider the following statement: \u201cNo two integers can be added together to form a fraction.\u201d In order to validate this claim with a direct or indirect proof, we would have to check every pair of integers and make sure that their sums do not yield a fraction. There are infinitely many integer pairs to check, so it is impossible to check them all. Instead, a method called proof by contradiction would be much more efficient.<\/p>\n<p>In a <strong>proof by contradiction<\/strong>, you establish the hypothesis (the given statements) of the proof, then make a statement saying \u201csuppose the claim is <em>not<\/em> true.\u201d From here, you would follow the logical implications of that \u201cnot\u201d statement. Eventually, you would come to some later statement which directly contradicts one of the earlier statements in the proof.<\/p>\n<p>For example, if we assume that \u201cthere are two integers whose sum is a fraction,\u201d then the eventual logical implication of that would be that one or both of those numbers were not integers at all. This forms a contradiction with the hypothesis that two integers are being examined, and this contradiction nullifies the supposition that the claim was false. As a result, it is proven by contradiction that the claim was true after all.<\/p>\n<p>Another proof method, which has a similar name but a different technique, is called <strong>proof by contraposition<\/strong>. In order to utilize this method, we must understand conditional statements, their negations, and their reversals. Conditional statements are \u201cif-statements\u201d and are usually given in the format \u201cif <em>this<\/em>, then <em>that<\/em>.\u201d For example, \u201cIf it is a holiday, then there is no school.\u201d We can switch the order of the conditional statement if we negate both sides. This gives an equivalent statement, \u201cIf there <em>is<\/em> school, then it is <em>not<\/em> a holiday.\u201d<\/p>\n<p>More formally, we can write this idea as \u201c<em>p<\/em> implies <em>q<\/em>\u201d is equivalent to \u201cnot-<em>q<\/em> implies not-<em>p<\/em>.\u201d <\/p>\n<div class=\"examplesentence\">\\(p\\rightarrow q \u21d4 ~q\\rightarrow ~p\\)<\/div>\n<p>\n&nbsp;<\/p>\n<p>We use tildes, or squiggles, to denote the negation of <em>p<\/em> and <em>q<\/em>. So just like \u201choliday\u201d implies \u201cno school,\u201d \u201cyes school\u201d implies \u201cno holiday.\u201d<\/p>\n<div class=\"examplesentence\">\\(\\text{Holiday} \\rightarrow \\text{no school}    \u21d4    \\text{school} \\rightarrow \\text{no holiday}\\)<\/div>\n<p>\n&nbsp;<\/p>\n<p>So, if you find yourself having trouble proving a conditional \u201cif <em>p<\/em>, then <em>q<\/em>\u201d statement, try rewriting the claim as \u201cif not<em>-q<\/em>, then not<em>-p<\/em>.\u201d This method of proof by contraposition can sometimes simplify the steps needed in a proof!<\/p>\n<p>The last method we will discuss is proof by induction. This technique is used whenever you need to show that some claim is true for an infinite number of cases. For example, consider the following claim: \u201cFor every positive integer n greater than or equal to 2, \\(n\\lt (n+1)(n-1)\\).\u201d<\/p>\n<p>To prove this claim, we would seemingly need to test every single integer greater than or equal to 2. But because that would take an infinite amount of time, proof by induction must be used.<\/p>\n<p>There are three steps in proof by induction. First, you must prove that the base case is true. For this claim, the base case would be \\(n=2\\), because that is the first time the claim applies. Let\u2019s prove that now.<\/p>\n<div class=\"examplesentence\">Let \\(n=2\\).<br \/>\n&nbsp;<br \/>\nThen we have \\(2\\lt  (2+1)(2-1)\\)\u2026<br \/>\n&nbsp;<br \/>\n\\( 2\\lt (3)(1)\\) <br \/>\n&nbsp;<br \/>\n\\( 2\\lt 3\\) <\/div>\n<p>\n&nbsp;<\/p>\n<p>Because it is true that \\(2\\lt 3\\), the claim is true in the base case \\(n=2\\).<\/p>\n<p>The second step in proof by induction is assuming that the claim is true for the case \\(n=k\\). <\/p>\n<div class=\"examplesentence\">Suppose that the claim is true for \\(n=k\\).<\/p>\n<p>Then \\(k\\lt (k+1)(k-1)\\).<\/p>\n<\/div>\n<p>\n&nbsp;<\/p>\n<p>This will help in the third step, which is proving that because the claim works for the \\(n=k\\) case, it must also work for the successive \\(n=k+1\\) case. If this part can be proven, then it is consequentially shown that the claim is true for any case \\(n\\geq 2\\).<\/p>\n<div class=\"examplesentence\">Is \\(k+1\\lt (k+1+1)(k+1-1)?\\)<\/div>\n<p>\n&nbsp;<\/p>\n<p>Notice from our previous statement that anywhere we had a \\(k\\) we replaced it with \\(k+1\\). Now we&#8217;re going to simplify.<\/p>\n<div class=\"examplesentence\">\\(k+1\\lt (k+2)(k)\\)<\/div>\n<p>\n&nbsp;<\/p>\n<p>Then we can move our 1 to the right side by subtracting 1 from both sides.<\/p>\n<div class=\"examplesentence\">\\(k\\lt (k+2)(k)-1\\)<\/div>\n<p>\n&nbsp;<\/p>\n<p>Now we can distribute our \\(k\\).<\/p>\n<div class=\"examplesentence\">\\(k\\lt k^{2}+2k-1\\)<\/div>\n<p>\n&nbsp;<\/p>\n<p>Now we can factor \\(k^{2}-1\\).<\/p>\n<div class=\"examplesentence\">\\(k\\lt (k+1)(k-1)+2k\\)<br \/>\n&nbsp;<\/p>\n<p>Because it was stated earlier that \\(k\\lt (k+1)(k-1)\\), and because \\(2k\\) is positive, it must be true that \\(k\\lt (k+1)(k-1)+2k\\).<br \/>\n&nbsp;<br \/>\nTherefore, the \\(n=k+1\\) case of the claim is proven.<\/div>\n<p>\n&nbsp;<\/p>\n<p>We finish the proof by stating:<\/p>\n<div class=\"examplesentence\">By induction, the claim that \\(n\\lt (n+1)(n-1)\\) for all \\(n\\geq 2\\) is proven to be true.\t<\/div>\n<p>\n&nbsp;<\/p>\n<p>Proof by induction is a helpful method for proving claims that apply to infinite integer cases. To use proof by induction, we started by proving that the claim was true in the base case, then we assumed that it was also true in the \\(n=k\\) case. Finally, we showed that this implied that the claim was true in the \\(n=k+1\\) case.<\/p>\n<p>Proofs are used by mathematicians to verify claims about the behaviors of different functions and to validate theorems which can be used in further research. Students perform mathematical proofs to better understand why these functions and theorems work and why they are trustworthy. Proofs are also great tools for engaging an active mind with logical thought.<\/p>\n<p>While proofs are typically regarded as difficult exercises, they are also very rewarding when completed. Now that you have an idea of how the different types of proofs are generally structured, you\u2019ll soon be completing proofs of your own.<\/p>\n<p>I hope that this video was helpful. Thanks for watching, and happy studying!<\/p>\n<\/div>\n<\/div>\n\n<p><a href=\"https:\/\/www.mometrix.com\/academy\/discrete-math\/\"><strong>Return to Discrete Math Videos<\/strong><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Introduction to Proofs Return to Discrete Math Videos<\/p>\n","protected":false},"author":22,"featured_media":168722,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":{"0":"post-168719","1":"page","2":"type-page","3":"status-publish","4":"has-post-thumbnail","6":"page_category-discrete-math-videos","7":"page_category-video-pages-for-study-course-sidebar-ad","8":"page_type-video"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.mometrix.com\/academy\/wp-json\/wp\/v2\/pages\/168719","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mometrix.com\/academy\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mometrix.com\/academy\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mometrix.com\/academy\/wp-json\/wp\/v2\/users\/22"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mometrix.com\/academy\/wp-json\/wp\/v2\/comments?post=168719"}],"version-history":[{"count":6,"href":"https:\/\/www.mometrix.com\/academy\/wp-json\/wp\/v2\/pages\/168719\/revisions"}],"predecessor-version":[{"id":281456,"href":"https:\/\/www.mometrix.com\/academy\/wp-json\/wp\/v2\/pages\/168719\/revisions\/281456"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.mometrix.com\/academy\/wp-json\/wp\/v2\/media\/168722"}],"wp:attachment":[{"href":"https:\/\/www.mometrix.com\/academy\/wp-json\/wp\/v2\/media?parent=168719"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}