Applications of Proof Techniques


A substantial learning aspect for any software engineers, in addition to the academia of computer science, is a topic called discrete mathematics. It is a branch of math that focuses on studying mathematical structures that are discrete (distinct and separate) in nature rather than continuous in nature (calculus, trigonometry). It is also an abstract form where conclusions are based on logical deductions using set theory and other simple theorems. Last spring, I took “Proof Techniques” as part of my CS major. The class is an introduction to proof writing techniques, covering multiple topics such as logic and proofs, set theory, mathematical induction, relations, modular arithmetic, functions, cardinality, number theory, and calculus.


As tense as that sounds, I certainly did learn a lot. Several concepts that stick to me the most are the 3 proofs approaches – direct, contrapositive, by contradiction – as well as math induction. Direct proof operates under the first-order logic: “If p, then q” and is a straightforward combination of established facts, existing lemmas and theorems, without making further assumptions. Contrapositive proof follows “If not q, then not p” and carries the same meaning as the “If p, then q” statement. Proof by contradiction goes the other way around: If a statement was considered true, a logical contradiction then occurs, hence the statement must be false. And finally, math induction is similar to recursion in computer science (with a base case and an inductive step) that’s all about reasoning from simpler cases to more complex cases, as long as the property under investigation travels upwards.

As part of my habit to deduce real-life applications from academics, I spent the last 3 hours brainstorming and seeking connections between these complex mathematical concepts to my professional life. Here are my attempts on that:

1 – Math Induction: Imagine you have a long chain of dominoes and you want to figure out which dominoes will fall over: (1) You begin by asserting that the first domino will fall over, presumably because you will push it, and (2) You say that any domino will fall if the domino before it knocks over (assuming your chain is well-crafted). From these two claims, you can show that any domino will fall over.

falling dominoes

Recently, I read this article in TechCrunch talking about how the tech industry is in a gigantic bubble: Raising funding for tech startups has never been so easy. Access to the unicorn club (companies with a valuation above $1 billion) has become increasingly less exclusive in the last 5 years. Companies themselves are burning through cash like there is no tomorrow. Angel investors and crowd funders do not think twice about valuations and liquidity in their investments. The article illustrates an example of Uber, undoubtedly the hottest business in the world right now, on the dynamics of a tech bubble. Everything has been going well for Uber: the explosion of the “sharing economy,” attraction to a large variety of investors, increased valuation between funding rounds… But now profitability is becoming less certain, because of the regulatory burdens and lawsuits the business is facing (I’m talking about the California law statement that all Uber drivers must now be treated as employees, not as contractors). The next phase is panic, and no one wants to see that.

Like I mentioned earlier, math induction refers to the sequential effect of failing dominoes. If Uber is the base case, then what will be the result of the inductive step?

2 – Contraposition: Different from direct proof, contrapositive proof is helpful when an implication has multiple hypotheses, or when the hypothesis specifies multiple objects. How one goes about deciding to prove directly or contra-positively? Well, one has to try both ways, just for a couple of steps, and see if either looks notably easier than the other.

A few weeks ago, I met with a Denison alumni from the 80s who is currently managing the Finance Operations department at Amazon. Before working here, he has spent 17 years at Starbucks doing all sort of business development and supply chain management stuffs. One of the advices he gave to me is to consider my personality very carefully for an entry-level job. Starbucks is a nurturing environment, where employees seek harmony and build relationships in order to move in the same direction. In contrast, Amazon is a cutthroat environment, where you got thrown in with very little training and have to learn to navigate and thrive competitively. Starbucks might sound more appealing, but Amazon is the way of life.


For job seekers, finding a job is not that direct as you think, sometimes you have to go the “contra-posed” way to seek out the best opportunities.

3 – Contradiction: The problem with proof by contradiction is that it isn’t “clean” – lack of elegance, understanding, and pedagogy. Another problem is that by default, proof by contradiction are non-constructive existence proofs: you assume it doesn’t exist and draw a contradiction, and therefore you conclude it does exist. Knowing something has to exist may be helpful in some way, but you can’t do anything with it if you don’t know how to find it.

At Koru, I spent 1 ½ weeks working on an employer challenge for Zillow, the biggest real estate data company in the US. A prominent feature of Zillow services is Zestimate, the estimate value of a specific property in the local market. While cold-calling real estate agents to gather customer discovery data for the challenge, we found out that many of them complained about the accuracy of Zestimate, which is inconsistent with market price. Now later on, while meeting with a data scientist / head of economics research at Zillow, I learned how Zestimate is computed using machine learning – engineers train algorithms with closing data of home attributes (which is guarded by brokers/MLSs or delayed in public record). Nevertheless, valuation is more art than science and a lot of what Zillow’s machine learning does is more about intelligently averaging valuations from other proprietary valuations from market leaders that supply valuations to mortgage lenders and insurance companies.

So to oppose the complaints about Zestimate inaccuracy, Zillow showcases the fancy machine learning approach that they use as a form of contradiction. But as valuation is artistic, that very much resembles the non-constructive proof, and we go back to ask: “How really accurate is the Zestimate?”


I guess that’s enough of me rumbling over the applications of proof techniques. My main insight is this: In the business world of unprecedented complexities, mathematics is the best way to predict and justify our reasoning.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s