Integer Sequences and the Need for Proof

This post over at Mr. Honner on unstated assumptions reminded me to share a great visual that shows some sequences are not what they seem:

Of course, the pattern that jumps out is:

2, 4, 8, 16, 32, 64, …

Geometric Sequence!  Exponential function!  2^(n-1).  HOWEVA,

I have yet to bust this out in my classroom, but I envision it being my answer the question “Why do we need proofs?”  Without proof or a counterexample, it is awfully easy to assume that a pattern exists when it really doesn’t.  That’s why we need proof.  Without being able to logically show something is true or false, you can fall into the traps of assumption.

I think I like the idea of setting up students to fail here. Just give them the question and let them try to find the pattern. Of course, their assumption will be that they can find a pattern and I’m sure most would be satisfied that 2^n works with n=1, 2, 3, 4, so it must work with all n.  As Lee Corso would say, “Not so fast my friend.”

Update

Thanks to commenter Graeme McRae for pointing out this sequence on OEIS (Online Encyclopedia of Integer Sequences).  The sequence can also be defined as the sum of the first five terms of the nth row of Pascal’s triangle:

Update #2

Andy Huynh notes that this sequence should be specified as the maximum number of regions created by putting n points on a circle and connecting them with chords.  As I mentioned in my comment, I think this observation again highlights the need to be able to prove something.  Andy notes that if you evenly space the points when n = 6 (create a regular hexagon), then you will end up with only 30 regions, not 31.  In fact, that’s what I did when I first did this problem which was shared at NCTM by Jen Szydlik.

6 thoughts on “Integer Sequences and the Need for Proof”

• Thanks! I LOVE that this sequence is the sum of the first 5 terms of the nth line of Pascal’s triangle. So many connections here.

And thanks for sharing oeis.org… I did not know of it before now!

1. Ha! This is a classic “Not so fast my friend.” I think I did this a couple years ago, and the kids would try to draw bigger “pizzas” because they felt they miscounted or didn’t see a smaller section to make it 32.

Josh Zucker at our last math teachers’ circle shared this great sequence to illustrate the point of “never assume!”:

Say we have f(n) = n^2 + n + 41, so if…

n = 0, then f(n) = 41
n = 1, then f(n) = 43
n = 2, then f(n) = 47
n = 3, then f(n) = 53
n = 4, then f(n) = 61
n = 5, then f(n) = 71
n = 6, then f(n) = 83
n = 7, then f(n) = 97

One might conclude right about now that f(n) is always prime. As it turns out, f(n) continues to be prime for a long while… until n = 40. That’s the FIRST time a non-prime f(n) shows up!

Fun. Thanks, Tom.

• Ooh, that’s a great one! I’m starting to think of how these tricky sequences can be fit into some of my algebra curriculum.

Maybe this is a fun way to introduce function notation? It seems to always be a tricky subject, but I can see a sequence treasure hunt, if you will, where the goal is to “break” the sequence. You’re practicing function notation, making tables, but at the same time you’re looking for patterns and finding counter-examples without ever mentioning counter examples or proofs.

2. Andy Huynh says:

I just want to make an observation. Here, you are talking about the maximum amount of regions(actually you didn’t state that but you should since the way you place the points change the number of regions). If you notice in the 6 points case, the very middle region would not be there if the points were equally spaced. So that means the sequence of points equally spaced would create a different sequence. I wonder what kind of formula there would exist for that. At first, I thought it wouldn’t be that difference of a sequence and that a “center” region would disappear for every even term, but according to OEIS, for the maximum amount sequence is 1, 2, 4, 8, 16, 31, 57, 99, …, while the sequence for equally spaced points is 1, 2, 4, 8, 16, 30, 57, 88, …,

• Thanks for that observation Andy! Actually, the first time I tried this problem, I did exactly what you said: I even spaced the six points and came up with 30 regions.

I think it is yet another good example of proof:

Imagine giving this to students and they come up with the 30 regions when n = 6. Then, prod them: “How do you know there are not more?” Perhaps, then some will find region #31. Prod again “How do you know there are not more?” Some might talk about the intersection of the three middle points but it again comes back to “How can we prove this is the most.”

Thanks again for the comment!