Thursday, April 23, 2015

Fencepost errors!

The other day I was surfing the net and I came up with couple of interesting problems that one of which is Fencepost error. To be honest I have never heard the word itself before, so thought of sharing it here! The name comes from a sort of simple tricky question that illustrates the error. If you are building a fence with fence posts that are 10 feet apart, and you want to build the fence to be 100 feet long, how many fence posts do you need?  10 comes out as a first intuitive answer which is quite WRONG! The fence needs to have 10 intervals between posts, and the extra post is needed to begin the first interval, so we need 11 fence in total. Our first answer was off by one and thats why the term "off-by-one'' is used exchangeably for this error.

Fencepost errors are the most common programming mistakes. The technique of extreme cases helps us to find and fix the bugs come from these counting problems.

  • Example:
 Consider the sum of the first n odd integers:

S=\underbrace{1+3+5+\hdots}_\text{n terms}
Odd numbers are of the form 2k+1 or 2k-1 . Now, how would you answer this question! Is the last number 2n+1 or 2n-1?

For general n , the answer is not obvious. You can figure it out, but it is easy to make an algebra mistake and be off by one term, which is the difference between 2n-1 and 2n+1. An extreme case settles the question. Here is the technique how to do it.

  1. Pick an extreme value of n , one where the last term in the sum is easy to determine.

  2. For that n , determine the last term.

  3. See which prediction, 2n-1 or 2n+1 is consistent with this last term.

  4. The most extreme value of n is 0. Since n is the number of terms, however, the n=0 does not make sense here. The next most extreme case is n=1 . With only one term the final term is 1, which is 2n-1 . So the final term, in general, is 2n-1. Therefore, the sum is
    S=1+3+5+\hdots+ 2n-1
Employing the sigma notation, it is
S=\sum_{k=0}^{n-1} (2k+1.)
This could be helpful in spotting the bugs in computer programmings.


  1. Hi Mina, do you know mathjax is installed on polystat?
    use \( )\ to write in-line latex ansd \[ ]\

  2. Hi, oh I didn't know! I made quite an effort to convert latex formulas to html! Thanks,

  3. It looks more attractive now... with the new images.