Proof by induction and proof by contradiction

This is the translation of an older post in French: Raisonnement par récurrence et raisonnement par l’absurde.

Let’s have a pretty short post so that I can refer to it later – I have another monster-post in the works, and I realized I needed the following elements to make it work, so here’s another post! I’m going to talk about two fundamental tools in the “proof toolbox”: the proof by induction and the proof by contradiction. These are tools that are explained in high school (well, they were in my French high school 20+ years ago 😉 ), and that you’ll see everywhere all the time, so let’s explain how it works.

Proof by induction

The idea of the induction proof is dominoes. Not the ones with the dots on them, the ones that you topple. You know that if you topple a domino, it falls. And if a domino falls, the next one falls as well. And you topple the first domino. Hence, all the dominoes fall.

Proofs by induction work in the same way. Suppose you have a property that depends on an natural number (positive integer), and you want to prove that it’s true for any natural number. First, you show that it’s true for a small natural number, say 0, 1 or 2 (sometimes the property doesn’t make much sense for 0 or 1). Then, you show that, if it’s true for a natural number k, it’s also true for k+1. So you have the “start” of the dominoes, the toppling (“it’s true for 0”), and the “chain” of dominoes (“if it’s true for k, it’s true for k+1“). If these two conditions are true, all the dominoes fall (“the property is true for all natural numbers greater than 0”).

Now this is where I’m a bit annoyed, because I have a an example that works, but the induction proof kind of sucks compared to another, which is much prettier. So I’m going to show both 😉

Suppose that I want to prove that the sum of all integers from 1 to n (that is to say, 1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n) equals \displaystyle \frac{n(n+1)}{2}. I start with n=1: \displaystyle \frac{1(1+1)}{2} = \frac 2 2 = 1, so the base case is true.

Now, I suppose that it’s true for an arbitrary natural number k that the sum of the integers from 1 to k is equal to \displaystyle \frac{k(k+1)}{2}, and I compute the sum of integers from 1 to k+1: 1 + 2 + 3 + ... + (k-1) + k + (k+1). This is equal to the sum of the integers from 1 to k, plus k+1. By induction hypothesis, this is equal to \displaystyle \frac{k(k+1)}{2} + k+1 = \frac{k^2 + k + 2k + 2}{2} = \frac{k^2 + 3k + 2}{2}. For my proof to work out, I want the sum of integers from 1 to k+1 to be equal to \displaystyle \frac{(k+1)(k+2)}{2}. And it so happens that (k+1)(k+2) is precisely equal to k^2 + 3k + 2.

So I have my base case, my induction step, and I proved exactly what I wanted to prove.

Now for the alternative, prettier proof. You consider a table with two lines and n columns:

1  2   3   4  ... n-2 n-1 n
n n-1 n-2 n-3 3 2 1

and you compute the sum of all the numbers in the table. You can add up, for each column, both lines. Every column sums to n+1: it’s the case for the first column, and at each step, you remove 1 from the first line, and you add 1 to the second line, so the sum stays the same (there’s actually a “hidden” induction proof in there!) There are n columns, so if I add all these results, it sums to n(n+1). But if I group the sum in a different way, the first line is equal to the sum of integers from 1 to n, the second line as well… so n(n+1) is two times the sum of the integers from 1 to n, which concludes the proof.

Proof by contradiction

Proofs by contradiction are sometimes dangerous, because they’re often misused or overused. I know some mathematicians who argue that a proof by contradiction is not very elegant, and that when one arises, it’s usually worth it to make the extra effort to try to turn it around in a non-contradiction proof. I still like the reasoning behind it, and it sometimes makes life much easier.

We want to prove that a proposition A is true. To prove A by contradiction, you make the hypothesis that A is false, you unroll a series of consequences that would be implied by the fact that A is false, and you arrive at something that you know is impossible. And if the fact that A is false implies an impossibility, it means that A is true, otherwise the universe collapses and it’s messy.

My favorite example is to prove that \sqrt 2 is irrational, that is to say that you can’t write it as \displaystyle \frac p q where p and q are integers.

I need a tiny preliminary lemma: I’m claiming that if an integer n is even, then its square n^2 is even, and that if n^2 is even, then n is even. If n is even, I can write n = 2k (with k integer). Then n^2 = 4k^2 = 2 \times 2k^2, so n^2 is even. If n is odd, I can write n = 2k+1, so n^2 = 4k^2 + 2k + 1 = 2(2k^2 + k) + 1, so n^2 is odd. So, if n^2 is even, then it can’t be that n would be odd (because otherwise n^2 would be odd as well), so n is even.

Now back to the irrationality of \sqrt{2}. We make the hypothesis that we can write \displaystyle \sqrt 2 = \frac p q. We can also make the assumption that the fraction is irreducible, because if it’s not, you can reduce it so that it is, so let’s assume that it’s the one we took from the beginning. (Note: a fraction \displaystyle \frac p q is irreducible if there is no integer k \geq 2 such that p and q are both divisible by k. If k exists, we divide p and q by k, and we get the fraction \displaystyle \frac{p/k}{q/k}).

So: I can write that \sqrt 2 \times q = p. If I square this equality, I get 2q^2 = p^2. Since q is an integer, q^2 is an integer, so p^2 is an even number (because it’s equal to twice an integer). But then, if p^2 is even, then p is even as well, according to my preliminary lemma. So I can write p = 2k and consequently p^2 = 4k^2. But then, since 2q^2 = p^2 = 4k^2, I can also write q^2 = 2k^2, so q^2 is even, so q is even as well. But that’s not possible: \displaystyle \frac p q is irreducible, so p and q cannot be both even! So something is wrong in my reasoning, and the only thing that can be wrong is my initial hypothesis, that is \sqrt{2} is rational. Hence, \sqrt{2} is irrational. Cute, isn’t it?

Peter Bence in Zürich / Theater 11

On Tuesday, we went to the Zürich concert of Peter Bence. Peter Bence is a Hungarian pianist who gained his fame with piano covers/arrangements – I particularly like his Don’t Stop Me Now and his Bad. Generally speaking, the guy is impressive. He also happens to have held the record of the fastest piano hitting (with 765 hits in a minute 🙂 )

So when a friend mentioned to me that he was coming to Switzerland, I hesitated a bit, and finally went “why not” and bought a couple of tickets for the Zürich show. And I didn’t regret it 🙂

We got treated with two hours of a great show – an alternance of known covers, original pieces, and Bence discussing what he was doing and joking around with the audience. I’ve had a few favorite pieces during the evening: the John Williams medley, the Don’t Stop Me Now (with a bit of Bohemian Rhapsody) and the original piece he called Fibonacci. I was, however, not super convinced by his Somebody to Love – I assume it’s musically good, but to me it felt “messy” and didn’t trigger the “right” emotional response for me, I think.

On the “non-strictly-musical” part of the show, the audience was also asked to contribute during another original piece to clap our hands after a given musical phrase – that was fun, and everybody played the game… even when it came back a bit later. The “lighting” part of the show was also very impressive and working very well.

Theater 11 is not a very large venue (but I think I’ve only been to Hallenstadion in Zürich so far, which is… essentially 10 times larger), which I liked, because even when booking late (and with a low number of places left), we still had pretty good seats. However, there was some issues with the sound system (apparently worse from Bence’s perspective than from ours). I was kind of disturbed at the beginning by a low… hum, I guess, in the speakers – whether it disappeared or I got used to it quickly, I can’t say 🙂

Generally speaking, it was a very, very enjoyable experience, the show was great, and I’m really looking forward to Peter Bence’s album. And to re-listen to what’s on YouTube in the meantime 😉 And if you have the opportunity to see the show: it’s worth it!

52Frames – Week 15 – Blue Hour

I’ve been waiting for reasonable weather all week last week to shoot Blue Hour for 52Frames. That… kind of didn’t happen, so Sunday evening came and I still didn’t have a shot. I was determined to not let my streak end, so this one is somewhat of a placeholder, I guess – it’s not what I would have wanted to get for this theme, but it’s what I got!

I had a first pretty bad shot with a bike traveling in that red/copper light, so I waited a bit for another bike to appear, and it worked out 🙂 The weather on top of the Uetliberg was actually pretty nice, in a foggy/ethereal way.

I don’t think it was quite the blue hour yet when I shot the picture – I compensated a bit in post-processing by giving a bit of a bluer tone, as well as boosting the reds to have a better contrast on the light in the street.

52Frames – Week 14 – Food Photography

The theme for last week’s 52Frames was Food Photography. I’ve taken enough pictures for our food blog that I know what I like and how to get at least decent food pictures. Since natural light is the main ingredient of that, and since we don’t have that much of that at dinner time, it kind of meant “lunch picture”. Our typical meals may not necessarily be the most appetizing because they may lack structure, so I chose to go for a simple one, with literally no cooking and just setting things up on the plate – avocado and salmon 🙂

T.I.M.E Stories

The first time we heard about T.I.M.E Stories was at Essen SPIEL 2015, where the publisher had a fairly impressive booth, all white, closed from the exterior as to avoid spoilers, and that seemed to have a fair amount of success. We didn’t get to play there, but it was definitely enough to put the game on the “I’m intrigued” list (marketing ploy: successful).

The base of the game is that the players are part of a time travelling agency, and they get sent to various missions as characters of the situation that they need to fix. As far as I can tell, the probability of finishing a given scenario on the first try is very low – and would probably require a lot of luck. But what T.I.M.E Stories does really well is that, since we’re within the framework of time travelling, all the information that the players have can be re-used in the subsequent runs of the scenarios. Consequently, a game of T.I.M.E Stories consists of one or several runs of a scenario, until the players figure out the whole story and achieve the scenario’s goal – how to achieve the “perfect run” that allows them to unlock the victory conditions. A scenario that is played through does not have any replayability, but there’s around 10 official scenarios, with more to come.

T.I.M.E Stories is more of a “framework” than a game: the base box provides a generic board, tokens, pawns, and base mechanics, as well as a single scenario, Asylum. Scenarios are essentially a deck of cards that player explore according to the framework rules, and define the use of the tokens, as well as any additional rule. The base box also provides a way to “save” the state of a game between two runs. Since we’ve always played through all the runs of a scenario in one afternoon, we haven’t used that feature at all, but I really like the idea!

We’ve played four scenarios (Asylum, The Marcy Case, Prophecy of Dragons, and Under the Mask) and I’m happy to report it’s always been an enjoyable experience. To me, it’s actually fairly close to an investigative game-master-less RPG. There’s obviously little to no leeway for crazy shenanigans and weird plans that are doomed from the beginning, but the whole feeling of solving a narrative puzzle as a team is definitely there. If that makes sense, I also get the same kind of “fatigue” after playing T.I.M.E Stories than I get from an RPG session (as a player), which makes me think that it probably scratches the same kind of itch.

The only point that could be improved in my view is that the rules feel sometimes slightly too fiddly when it comes to handling the time limit of a mission. We’ve had to check them multiple times in the last session because we were not sure if we had to spend a unit of time or not to make certain actions, and that’s a bit annoying. There’s also the feeling that the expansions differ with one another when it comes to the clarity of the extra/specific rules.

But all in all, it’s a solid experience and a very pleasant way to spend an afternoon with friends.

52Frames – 2019 Weeks 12 and 13 – “Old” and “New”

I forgot to post last week’s 52Frames, so I’m doing two posts in one!

This was my entry for “Old“. I bought flowers for another project (and because I wanted flowers), and they wilted (half on purpose because I knew this could work for the “Old” theme. I actually took a bunch of picture of that one, and this one was the one I preferred for that theme. (I have another one that I like a lot and for another theme, but shhhh, it’s still a secret for a few weeks!)

My entry for “New” is definitely in the “consistency shots” category – that is, a wholly uninspired picture that kind of fits the theme, for the sole purpose of not breaking the streak. So: I did not break my streak (this was my 13th week in a row, woo!), and also we have new plates and cutlery 😛

#balisebooks – March 2019

(Version française ici : #balisebooks – Mars 2019)

Wicked Sweet – Chelsea M. Cameron

Dove is a student in business school, and she has A Plan for what happens next – she works at developing her own personal brand, and she works as a media consultant to pay her bills. And then one day, her high school arch-nemesis, Seven, appears in the same college, and they end up needing to cooperate on a school project. Seven also has A Plan: she eventually wants to open a goth-themed bakery, and she needs a bit of help testing her creations. Wicked Sweet is a super cute romance book and I really enjoyed it – it may lack a bit in the “plot” and “tension” department, but I really liked the characters 🙂

Happiness for Humans – P.Z. Reizin

Jen works for a software company: she talks to their star AI, Aiden, to teach it (or him) how to interact with people. Tom is a writer, and he also gets the attention of Aiden. Eventually, they both receive a e-mail from a mysterious “common friend” suggesting they should meet. The whole concept of a rom-com where AIs play a large role is pretty fun, and it’s mostly well-implemented in Happiness for Humans. But I was very disappointed by a couple of clichés that annoyed me to no end (specifically, the fact that software engineers are considered as “not entirely humans”, and referring to women as “the opposite species”… ugh.), making my reading of the book far less enjoyable than it could have been.

The Signal and the Noise: Why So Many Predictions Fail – But Some Don’t – Nate Silver

I didn’t finish this one – mostly because I needed to look forward to my commute reading at that time, and I wasn’t looking forward to continue reading this, because it felt fairly dry and the chapters were longer than my attention span. I think this is mostly a timing issue for me.

Nine Perfect Strangers – Liane Moriarty

A story that starts with nine people gathering in a luxury health resort, all with their history and their hope for transformation and a better life. The owner of the health resort is convinced to be able to help them – as long as the customers follow her lead. I liked the setting and most characters (although I had a hard time not conflating a couple of them because I messed up the name/character associations in my head), some parts made me chuckle, and some parts got a tear. I’m not necessarily convinced by the major plot point, but generally speaking it was a very pleasant read, and probably exactly what I needed then. Also: I actually missed my train stop the other day because I was distracted by my reading, which is probably a good sign for the book.

Nemesis Games – James S.A. Corey

Fifth book of The Expanse, the series that keeps delivering, even after 2800+ pages. The book starts with the Rocinante crew all getting on their merry way for various (temporary) reasons, and all ending up getting involved in various adventures and catastrophes. Nemesis Games is more centered on the “original cast” than the previous book, which I liked, because it was nice to have a bit more familiarity with the characters considering the large dramatic scale of the plot. To me, this series of books stays very solid; not necessarily very original or mind-blowing, but consistently good and worth reading, which is a feat in itself.

Geek Girl – Holly Smale

Harriet is a (very) geeky/nerdy highschooler who gets unexpectedly hired to be a fashion model. This is not the kind of premise where you expect a very believable book – and even under this assumption, I found myself requiring a higher effort than usual at suspension of disbelief. It was still pretty fun, and there were a few funny moments and a few touching moments, but there was definitely too much eye-rolling from my side to consider reading the second one any time soon.

La Papeterie Tsubaki – Ito Ogawa

This one is a Japanese book, that I read in French translation (there’s no English translation that I know of). The narrator, Hatoko, is a young woman who runs a stationary shop and who works as a public writer/calligrapher for people who have a hard time expressing what they want to say on paper. Most of the book, over the span of a year, is about the encounters between Hatoko and her customers, and the relationship of Hatoko with her trade – how she chooses her paper, ink, writing style to make the written word come to life. It’s a very contemplative and slow book, and it’s quiet and soothing. On a slightly negative standpoint, I was surprised by a few turns of sentences and choices of words, and dialogues sometimes felt weird. But generally speaking I really, really loved this book.