To disprove a theorem or a statement all you need is one counter example. Unfortunately, no number of examples supporting the theorem is sufficient to prove its correctness.
You can never really prove the proposition that “All swans are white” even if you have only seen white swans in your entire life. But you can certainly disprove the proportion by seeing a single black swan.
Proof by Contradiction is a powerful idea to have in your repertoire. To prove a theorem by contradiction we first assume that the theorem is false. We then find a logical contradiction arising from this assumption. The only way to resolve the contradiction is to conclude that the theorem must be true. Let us solve some problems using this technique.
1. There is no largest integer
Let us assume that there is a largest integer. Let us call it as N. Let C = N + 1. Since N and 1 are integers, C is also an integer. Why? Sum of two integers is an integer. Now C > N and N is no longer the largest integer. Hence our initial assumption is false and the theorem “There is no largest integer” is true.
2. For all integers n, if n ^ 2 is odd, then n is odd
Let us assume that n is even and n ^ 2 is odd. With this assumption
Since n is even we can write n = 2 * k from some integer k. Multiplying both sides by n we get n * n = (2 * k) * (2 * k) n * n = 2 * (2 * k * k) n * n = 2 * (some integer) n ^ 2 = 2 * (some integer)
We ended up with n ^ 2 being even. This means our assumption is false. Hence the theorem “For all integers n, if n ^ 2 is odd, then n is odd” is true.
3. Square root of 2 is an irrational number
A irrational number is a number that cannot be written as a simple fraction. Once again let us assume that sqrt(2) is a rational number. This means that it can be represented as a fraction. With that assumption
sqrt(2) = a / b 2 = (a ^ 2) / (b ^ 2) [squaring both the sides] (a ^ 2) = 2 * (b ^ 2) [This means a ^ 2 is even and a is also even] Since a is even we can write a = 2 * K; for some integer K. Substituting this value (2 * K) ^ 2 = 2 * (b ^ 2) 4 * (K ^ 2) = 2 * (b ^ 2) (b ^ 2) = 2 * (k ^ 2) [This means b ^ 2 is even and b is also even]
From the above both a and b are even. Since both are even they can be simplified further. This contradicts our assumption. Hence fraction a / b is not in lowest terms. Hence square root of 2 is an irrational number. This is all fine. We did study this in our school. How useful it is in real life? Recently I read the lecture notes from Prof. Sanjay Bakshi and he gave several real life examples. Given below are some of his examples.
Buffett on dotcoms
During the dotcom boom Berkshire Hathaway shares lagged the market. In 1999 Buffett lagged S and P 500 by 20.5%. This was his worst performance ever.
Someone asked him why he does not buy stocks in the internet companies. He explained it by using proof by contradiction.
When we buy a stock, we always think in terms of buying the whole enterprise because it enables us to think as businessmen rather than stock speculators. So let’s just take a company that has marvelous prospects, that’s paying you nothing now where you buy at a valuation of $500 billion. If you feel that 10% is the appropriate return and it pays you nothing this year, but starts to pay you next year, it has to be able to pay you $55 billion each year – in perpetuity. But if it’s not going to pay you anything until the third year, then it has to pay $60.5 billion each per year – again in perpetuity – to justify the present price… I question sometimes whether people who pay $500 billion implicitly for a business by paying some price for 100 shares of stock are really thinking of the mathematics that is implicit in what they’re doing. For example, let’s just assume that there’s only going to be a one-year delay before the business starts paying out to you and you want to get a 10% return. “If you paid $500 billion, then $55 billion in cash is the amount that it’s going to have to disgorge to you year after year after year. To do that, it has to make perhaps $80 billion, or close to it, pretax. Look around at the universe of businesses in this world and see how many are earning $80 billion pretax – or $70 billion or $60 or $50 or $40 or even $30 billion. You won’t find any.
Ralph Wanger on disk drive industry
Ralph Wanger, a successful money manager who used proof by contradiction to show why investing in the disk drive companies during 1980’s will not work. He wrote
Remember back in the early 80’s when the hard disk drive for computers was invented? It was an important, crucial invention, and investors were eager to be part of this technology. More than 70 disk drive companies were formed and their stocks were sold to the public. Each company had to get 20 percent of the market share to survive. For some reason they didn’t all do it.
Markopolos blew the whistle on Madoff
The Ponzi scheme orchestrated by Bernard L. Madoff was the largest fraud by anyone in American history, involving over $50 billion and damaging the finances of thousands. Victims were mainly individuals and charities. He was running this scheme for several years and everyone believed him.
Harry M. Markopolos is an American former securities industry executive and an independent forensic accounting and financial fraud investigator. Markopolos found out that Madoff is running a giant ponzi scheme. He alerted the Securities and Exchange Commission in 2000, 2001, and 2005. Watch the video on how he found out.
How long it took him to find out the fraud? It took five minutes to know that it was a fraud. He spent another four hours of mathematical modeling to prove that it was a fraud. How did he do this when everyone else did not have any clue. Madoff investment record showed that his investments always went up. Using proof by contradiction there are only two ways by which it is possible.
- You have insider information
- Giant ponzi scheme
Either case it is a fraud and it turned out to be a giant ponzi scheme.
Proof by Contradiction is a powerful tool and its use extends beyond academics.