# 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.

-

## marked as duplicate by Brian M. Scott, William, Rudy the Reindeer, J. M., NorbertOct 3 '12 at 20:11

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

## 1 Answer

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.

-
The solution you have posted it correct.But I am not able to understand how you framed f(n).Could you please elaborate it furthur. – g4ur4v Sep 11 '12 at 17:27