Category Archives: induction

PIE: proof by algebra

Posted on August 7, 2019 by Brent

In my previous post I stated a very formal, general form of the Principle of Inclusion-Exclusion, or PIE.1 In this post I am going to outline one proof of PIE. I’m not going to give a completely formal proof, because … Continue reading →

Posted in combinatorics, induction, pattern, proof | Tagged exclusion, formal, inclusion, induction, PIE, proof, sets | 2 Comments

Book review: Roads to Infinity

Posted on July 5, 2011 by Brent

What is infinity? What is proof? These are two of the biggest questions mathematicians have grappled with over the years. In this well-written and fascinating book, John Stillwell takes us on a tour through some of the answers to these … Continue reading →

Posted in arithmetic, books, computation, induction, infinity, logic, proof, review | Tagged infinity, John Stillwell, proof, roads | Comments Off

Cassini’s identity

Posted on May 15, 2011 by Brent

My previous post asked you to take any Fibonacci number, square it, and also multiply the two adjacent Fibonacci numbers, and see if a pattern emerged. Here’s a table I made for the first 6 Fibonacci numbers: (Hmm, the numbers … Continue reading →

Posted in algebra, fibonacci, induction, pattern, proof, solutions | Tagged Cassini, fibonacci, identity | 8 Comments

The hyperbinary sequence and the Calkin-Wilf tree

Posted on October 18, 2009 by Brent

And now, the amazing conclusion to this series of posts on Neil Calkin and Herbert Wilf’s paper, Recounting the Rationals, and the answers to all the questions about the hyperbinary sequence. Hold on to your hats! The Calkin-Wilf Tree First, … Continue reading →

Posted in arithmetic, computation, induction, iteration, number theory, pattern, proof, recursion, sequences, solutions | Tagged algorithm, binary, Calkin-Wilf, Euclidean, Haskell, hyperbinary, tree | 6 Comments

More hyperbinary fun

Posted on September 28, 2009 by Brent

When I originally posed Challenge #12, a certain Dave posted a series of comments with some explorations and partial solutions to part II (the hyperbinary sequence). Although I gave the “solution” in my last post, no solution to any problem … Continue reading →

Posted in challenges, induction, pattern, proof, recursion, sequences, solutions | Tagged hyperbinary, induction | 12 Comments

Challenge #12 solution, part II

Posted on September 19, 2009 by Brent

Yes, that’s right, that Challenge #12, posted one year, five months, and a day ago. You see, I have this nasty habit of starting things and not finishing them… well, better late than never! Question two of the aforementioned challenge … Continue reading →

Posted in challenges, counting, induction, pattern, sequences, solutions | Tagged binary, hyperbinary | 15 Comments

Recounting the Rationals, part IV

Posted on February 6, 2008 by Brent

Continuing a series about the Calkin-Wilf tree (see those links for some background), today I’d like to show why all the rationals in the tree must be in lowest terms. Let’s start off with a little number theory! What do … Continue reading →

Posted in induction, number theory, pattern, proof | 11 Comments

Golden powers

Posted on September 10, 2007 by Brent

So, we know from a previous challenge that . That’s a pretty interesting property, which is shared only by its cousin, . I wonder whether other powers of have special properties too? Let’s see: Interesting! What about ? And ? … Continue reading →

Posted in famous numbers, fibonacci, golden ratio, induction, proof | 6 Comments