The idea is to consider choosing double numbers from among the n choices, but with the second number not really being considered as in the chosen set. The problem is that if the last number, n, is to be chosen, we need n+1 to be part of the set to be chosen from. Also, when counting combinations, depending on the cardinality of the subset, the cardinality of the including set has to be artificially decreased.

For example, take the case of n=5. When choosing 2 out of these and we're using this combination approach, we need to go up to 6, that is, n+1. But the combinations are of only 2 out of 4:

1,3 considered as 12 34 5 6

1,4 considered as 12 3 45 6

1,5 considered as 12 3 4 56

2,4 considered as 1 23 45 6

2,5 considered as 1 23 4 56

3,5 considered as 1 2 34 56

That is we're choosing four objects, two of which are to be singletons and two as pairs, the second member of each pair being the number ineligible for inclusion.  Similarly for other numbers, when choosing r out of n, we really want C(n+1-r,r), as number n+1 has to be included to accommodate the nonused part of pairs, but each pairing cuts down on the number to be chosen from.

    4   kill "noneighb.txt"

    5   open "noneighb.txt" for output as #2

   10   for N=3 to 12:Tot=0

   20   for R=0 to N

   30     if R<=N-R+1 then Tot=Tot+combi(N-R+1,R)

   40   next

   50   print #2,N,Tot

   60   next

   70   close #2

   

Before running this, I thought I'd have to go to Sloane's OEIS with the results, but the output seems more obvious:   

   

 3   5 

 4   8 

 5   13 

 6   21 

 7   34 

 8   55 

 9   89 

 10   144 

 11   233 

 12   377 

   

These include the null set (r=0), choosing a subset with no members of the original set.

These are obviously the Fibonacci numbers F(n+2).