Category Archives: arithmetic

A combinatorial proof: PIE a la mode!

Continuing from my last post in this series, we’re trying to show that , where is defined as which is what we get when we start with a sequence of consecutive th powers and repeatedly take successive differences. Recall that … Continue reading

Posted in arithmetic, combinatorics, proof | Tagged , , , , , | Leave a comment

Order of operations considered harmful

[The title is a half-joking reference to Edsger Dijkstra’s classic paper, Go To Statement Considered Harmful; see here for more context.] Everyone is probably familiar with the so-called “order of operations”, which is a collection of rules that reflect conventions … Continue reading

Posted in arithmetic, teaching | Tagged , , , , , , | 7 Comments

A combinatorial proof: counting bad functions

In a previous post we derived the following expression: . We are trying to show that , in order to show that starting with a sequence of consecutive th powers and repeatedly taking successive differences will always result in . … Continue reading

Posted in arithmetic, combinatorics, proof | Tagged , , , , , | 1 Comment

A combinatorial proof: functions and matchings

We’re trying to prove the following equality (see my previous post for a recap of the story so far): In particular we’re trying to show that the two sides of this equation correspond to two different ways to count the … Continue reading

Posted in arithmetic, combinatorics, proof | Tagged , , , , , | 5 Comments

A combinatorial proof: the story so far

In my last post I reintroduced this seemingly odd phenomenon: Start with consecutive integers and raise them all to the th power. Then repeatedly take pairwise differences (i.e. subtract the first from the second, and the second from the third, … Continue reading

Posted in arithmetic, combinatorics, proof | Tagged , , , | 1 Comment

A combinatorial proof: reboot!

More than seven years ago I wrote about a curious phenomenon, which I found out about from Patrick Vennebush: if you start with a sequence of consecutive th powers, and repeatedly take pairwise differences, you always end up with , … Continue reading

Posted in arithmetic, combinatorics, proof | Tagged , , , | 11 Comments

Computing the Euler totient function, part 4: totient of prime powers

I’ve been on a bit of a hiatus as I’ve been travelling with my family for the past month. So here’s a recap. Our story so far Recall that the Euler totient function, , counts how many numbers from to … Continue reading

Posted in arithmetic, computation, counting | Tagged , ,