# Formula to calculate the sum of the series [duplicate]

Suppose there are n houses and I want to calculate the number of ways of selecting any number of houses given a condition that I have to select atleast three consecutive houses. for eg.if the total number of houses is 4,so the no of ways to do the job will be 3. No of houses(n)=4 no of ways = {1,2,3},{2,3,4},{1,2,3,4}

(note:I am can only select in increasing order of the number,so {1,3,2},etc are invalid)

I was able to find that total no of ways to do the above job follows a series

Sum=1+2+5+12+28+...(n-2) terms

so when n=4,then no of ways = 1+2=3 .When n=5,then no of ways=1+2+5=8 and so on.

Now,i am looking for the formula in terms of n to calculate the sum of this series.

• Please help me with the formula.I am stuck as this is the part of a programming problem that I am trying to solve. – g4ur4v Sep 8 '12 at 14:17
• – Hagen von Eitzen Sep 8 '12 at 14:31

Let $f(n)$ denote the number of subsets of $\{1, \ldots,n\}$ that avoid three consecutive numbers. Then what you are looking for is simply $2^n-f(n)$.
Clearly, $f(0)=1$, $f(1)=2$, $f(2)=4$. For $n\ge3$, such an avoiding set is either
• in fact a subset of $\{1,\ldots,n-1\}$
• of the form $A\cup \{n\}$ where $A\subseteq \{1,\ldots,n-2\}$
• of the form $A\cup \{n-1, n\}$ where $A\subseteq \{1,\ldots,n-3\}$
We conclude $f(n) = f(n-1) + f(n-2)+f(n-3)$ for $n\ge3$. These are the tribonacci numbers, see http://oeis.org/A000073 for some formulas to compute them and more information.