A007895 -id:A007895 - cp's OEIS frontend

A000120 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3

Offset: 0

N. J. A. Sloane

The binary weight of n is also called Hamming weight of n. [The term "Hamming weight" was named after the American mathematician Richard Wesley Hamming (1915-1998). - Amiram Eldar, Jun 16 2021]
a(n) is also the largest integer such that 2^a(n) divides binomial(2n, n) = A000984(n). - Benoit Cloitre, Mar 27 2002
To construct the sequence, start with 0 and use the rule: If k >= 0 and a(0), a(1), ..., a(2^k-1) are the first 2^k terms, then the next 2^k terms are a(0) + 1, a(1) + 1, ..., a(2^k-1) + 1. - Benoit Cloitre, Jan 30 2003
An example of a fractal sequence. That is, if you omit every other number in the sequence, you get the original sequence. And of course this can be repeated. So if you form the sequence a(0 * 2^n), a(1 * 2^n), a(2 * 2^n), a(3 * 2^n), ... (for any integer n > 0), you get the original sequence. - Christopher.Hills(AT)sepura.co.uk, May 14 2003
The n-th row of Pascal's triangle has 2^k distinct odd binomial coefficients where k = a(n) - 1. - Lekraj Beedassy, May 15 2003
Fixed point of the morphism 0 -> 01, 1 -> 12, 2 -> 23, 3 -> 34, 4 -> 45, etc., starting from a(0) = 0. - Robert G. Wilson v, Jan 24 2006
a(n) is the number of times n appears among the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421. - Jeremy Gardiner, Jan 25 2006
a(n) is the number of solutions of the Diophantine equation 2^m*k + 2^(m-1) + i = n, where m >= 1, k >= 0, 0 <= i < 2^(m-1); a(5) = 2 because only (m, k, i) = (1, 2, 0) [2^1*2 + 2^0 + 0 = 5] and (m, k, i) = (3, 0, 1) [2^3*0 + 2^2 + 1 = 5] are solutions. - Hieronymus Fischer, Jan 31 2006
The first appearance of k, k >= 0, is at a(2^k-1). - Robert G. Wilson v, Jul 27 2006
Sequence is given by T^(infinity)(0) where T is the operator transforming any word w = w(1)w(2)...w(m) into T(w) = w(1)(w(1)+1)w(2)(w(2)+1)...w(m)(w(m)+1). I.e., T(0) = 01, T(01) = 0112, T(0112) = 01121223. - Benoit Cloitre, Mar 04 2009
For n >= 2, the minimal k for which a(k(2^n-1)) is not multiple of n is 2^n + 3. - Vladimir Shevelev, Jun 05 2009
Triangle inequality: a(k+m) <= a(k) + a(m). Equality holds if and only if C(k+m, m) is odd. - Vladimir Shevelev, Jul 19 2009
a(k*m) <= a(k) * a(m). - Robert Israel, Sep 03 2023
The number of occurrences of value k in the first 2^n terms of the sequence is equal to binomial(n, k), and also equal to the sum of the first n - k + 1 terms of column k in the array A071919. Example with k = 2, n = 7: there are 21 = binomial(7,2) = 1 + 2 + 3 + 4 + 5 + 6 2's in a(0) to a(2^7-1). - Brent Spillner (spillner(AT)acm.org), Sep 01 2010, simplified by R. J. Mathar, Jan 13 2017
Let m be the number of parts in the listing of the compositions of n as lists of parts in lexicographic order, a(k) = n - length(composition(k)) for all k < 2^n and all n (see example); A007895 gives the equivalent for compositions into odd parts. - Joerg Arndt, Nov 09 2012
From Daniel Forgues, Mar 13 2015: (Start)
Just tally up row k (binary weight equal k) from 0 to 2^n - 1 to get the binomial coefficient C(n,k). (See A007318.)
     0   1       3               7                              15
  0: O | . | .   . | .   .   .   . | .   .   .   .   .   .   .   . |
  1:   | O | O   . | O   .   .   . | O   .   .   .   .   .   .   . |
  2:   |   |     O |     O   O   . |     O   O   .   O   .   .   . |
  3:   |   |       |             O |             O       O   O   . |
  4:   |   |       |               |                             O |
Due to its fractal nature, the sequence is quite interesting to listen to.
(End)
The binary weight of n is a particular case of the digit sum (base b) of n. - Daniel Forgues, Mar 13 2015
The mean of the first n terms is 1 less than the mean of [a(n+1),...,a(2n)], which is also the mean of [a(n+2),...,a(2n+1)]. - Christian Perfect, Apr 02 2015
a(n) is also the largest part of the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2, 2, 2, 1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - Emeric Deutsch, Jul 20 2017
a(n) is also known as the population count of the binary representation of n. - Chai Wah Wu, May 19 2020

			Using the formula a(n) = a(floor(n / floor_pow4(n))) + a(n mod floor_pow4(n)):
  a(4) = a(1) + a(0) = 1,
  a(8) = a(2) + a(0) = 1,
  a(13) = a(3) + a(1) = 2 + 1 = 3,
  a(23) = a(1) + a(7) = 1 + a(1) + a(3) = 1 + 1 + 2 = 4.
_Gary W. Adamson_ points out (Jun 03 2009) that this can be written as a triangle:
  0,
  1,
  1,2,
  1,2,2,3,
  1,2,2,3,2,3,3,4,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  1,2,2,3,2,3,...
where the rows converge to A063787.
From _Joerg Arndt_, Nov 09 2012: (Start)
Connection to the compositions of n as lists of parts (see comment):
[ #]:   a(n)  composition
[ 0]:   [0]   1 1 1 1 1
[ 1]:   [1]   1 1 1 2
[ 2]:   [1]   1 1 2 1
[ 3]:   [2]   1 1 3
[ 4]:   [1]   1 2 1 1
[ 5]:   [2]   1 2 2
[ 6]:   [2]   1 3 1
[ 7]:   [3]   1 4
[ 8]:   [1]   2 1 1 1
[ 9]:   [2]   2 1 2
[10]:   [2]   2 2 1
[11]:   [3]   2 3
[12]:   [2]   3 1 1
[13]:   [3]   3 2
[14]:   [3]   4 1
[15]:   [4]   5
(End)

Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 119.
Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589. - N. J. A. Sloane, Aug 03 2012
Manfred R. Schroeder, Fractals, Chaos, Power Laws. W.H. Freeman, 1991, p. 383.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Franklin T. Adams-Watters, and Frank Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS, Vol. 12 (2009), Article 09.5.6.
J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197. (PS file on author's web page.)
Jean-Paul Allouche, Jeffrey Shallit and Jonathan Sondow, Summation of Series Defined by Counting Blocks of Digits, arXiv:math/0512399 [math.NT], 2005-2006.
Jean-Paul Allouche, Jeffrey Shallit and Jonathan Sondow, Summation of series defined by counting blocks of digits, J. Number Theory, Vol. 123 (2007), pp. 133-143.
Richard Bellman and Harold N. Shapiro, On a problem in additive number theory, Annals Math., Vol. 49, No. 2 (1948), pp. 333-340. - _N. J. A. Sloane_, Mar 12 2009
C. Cobeli and A. Zaharescu, A game with divisors and absolute differences of exponents, Journal of Difference Equations and Applications, Vol. 20, #11 (2014) pp. 1489-1501, DOI: 10.1080/10236198.2014.940337. Also available as arXiv:1411.1334 [math.NT], 2014. See delta_n.
Jean Coquet, Power sums of digital sums, J. Number Theory, Vol. 22, No. 2 (1986), pp. 161-176.
F. M. Dekking, The Thue-Morse Sequence in Base 3/2, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22 (2015), #P2.24.
Josef Eschgfäller and Andrea Scarpante, Dichotomic random number generators, arXiv:1603.08500 [math.CO], 2016.
Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.
Steven R. Finch, Pascal Sebah and Zai-Qiao Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger and Robert F. Tichy, Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci., Vol. 123, No. 2 (1994), pp. 291-314.
Michael Gilleland, Some Self-Similar Integer Sequences.
P. J. Grabner, P. Kirschenhofer, H. Prodinger and R. F. Tichy, On the moments of the sum-of-digits function, Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), Kluwer Acad. Publ., Dordrecht, 1993, 263-271.
Ronald L. Graham, On primitive graphs and optimal vertex assignments, Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970, pp. 170-186.
Khodabakhsh Hessami Pilehrood and Tatiana Hessami Pilehrood, Vacca-Type Series for Values of the Generalized Euler Constant Function and its Derivative, J. Integer Sequences, Vol. 13 (2010), Article 10.7.3.
Nick Hobson, Python program for this sequence.
Kathy Q. Ji and Herbert S. Wilf, Extreme Palindromes, arXiv:math/0611465 [math.CO], 2006.
Guy Louchard and Helmut Prodinger, The Largest Missing Value in a Composition of an Integer and Some Allouche-Shallit-Type Identities, J. Int. Seq., Vol. 16 (2013), Article 13.2.2.
J.-L. Mauclaire and Leo Murata, On q-additive functions, I, Proc. Japan Acad. Ser. A Math. Sci., Vol. 59, No. 6 (1983), pp. 274-276.
J.-L. Mauclaire and Leo Murata, On q-additive functions, II, Proc. Japan Acad. Ser. A Math. Sci., Vol. 59, No. 9 (1983), pp. 441-444.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., Vol. 3 (1974), pp. 255-261.
Kerry Mitchell, Spirolateral-Type Images from Integer Sequences, 2013.
Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117, No. 7 (2010), pp. 581-598.
Theophanes E. Raptis, Finite Information Numbers through the Inductive Combinatorial Hierarchy, arXiv:1805.06301 [physics.gen-ph], 2018.
Carlo Sanna, On Arithmetic Progressions of Integers with a Distinct Sum of Digits, Journal of Integer Sequences, Vol. 15 (2012), Article 12.8.1. - _N. J. A. Sloane_, Dec 29 2012
Nanci Smith, Problem B-82, Fib. Quart., Vol. 4, No. 4 (1966), pp. 374-375.
Jonathan Sondow, New Vacca-type rational series for Euler's constant and its "alternating" analog ln 4/Pi, arXiv:math/0508042 [math.NT] 2005; Additive Number Theory, D. and G. Chudnovsky, eds., Springer, 2010, pp. 331-340.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Kenneth B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., Vol. 32 (1977), pp. 717-730. See B(n). - _N. J. A. Sloane_, Apr 05 2014
J. R. Trollope, An explicit expression for binary digital sums, Math. Mag., Vol. 41, No. 1 (1968), pp. 21-25.
Robert Walker, Self Similar Sloth Canon Number Sequences.
Eric Weisstein's World of Mathematics, Binary, Digit Count, Stolarsky-Harborth Constant, Digit Sum.
Wikipedia, Hamming weight.
Wolfram Research, Numbers in Pascal's triangle.
Index entries for "core" sequences
Index entries for sequences related to binary expansion of n
Index entries for Colombian or self numbers and related sequences
Index entries for sequences that are fixed points of mappings

The basic sequences concerning the binary expansion of n are this one, A000788, A000069, A001969, A023416, A059015, A007088.
Partial sums see A000788. For run lengths see A131534. See also A001792, A010062.
Number of 0's in n: A023416 and A080791.
a(n) = n - A011371(n).
Sum of digits of n written in bases 2-16: this sequence, A053735, A053737, A053824, A053827, A053828, A053829, A053830, A007953, A053831, A053832, A053833, A053834, A053835, A053836.
Cf. A001620, A344716, A007814, A063787.
This is Guy Steele's sequence GS(3, 4) (see A135416).
Cf. A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).
Cf. A230952 (boustrophedon transform).
Cf. A070939 (length of binary representation of n).

Fortran
```
c See link in A139351
```

import Data.Bits (Bits, popCount)
a000120 :: (Integral t, Bits t) => t -> Int
a000120 = popCount
a000120_list = 0 : c [1] where c (x:xs) = x : c (xs ++ [x,x+1])
-- Reinhard Zumkeller, Aug 26 2013, Feb 19 2012, Jun 16 2011, Mar 07 2011

a000120 = concat r
    where r = [0] : (map.map) (+1) (scanl1 (++) r)
-- Luke Palmer, Feb 16 2014

[Multiplicity(Intseq(n, 2), 1): n in [0..104]]; // Marius A. Burtea, Jan 22 2020

[&+Intseq(n, 2):n in [0..104]]; // Marius A. Burtea, Jan 22 2020

A000120 := proc(n) local w,m,i; w := 0; m := n; while m > 0 do i := m mod 2; w := w+i; m := (m-i)/2; od; w; end: wt := A000120;
A000120 := n -> add(i, i=convert(n,base,2)): # Peter Luschny, Feb 03 2011
with(Bits): p:=n->ilog2(n-And(n,n-1)): seq(p(binomial(2*n,n)),n=0..200) # Gary Detlefs, Jan 27 2019

Table[DigitCount[n, 2, 1], {n, 0, 105}]
Nest[Flatten[# /. # -> {#, # + 1}] &, {0}, 7] (* Robert G. Wilson v, Sep 27 2011 *)
Table[Plus @@ IntegerDigits[n, 2], {n, 0, 104}]
Nest[Join[#, # + 1] &, {0}, 7] (* IWABUCHI Yu(u)ki, Jul 19 2012 *)
Log[2, Nest[Join[#, 2#] &, {1}, 14]] (* gives 2^14 term, Carlos Alves, Mar 30 2014 *)

{a(n) = if( n<0, 0, 2*n - valuation((2*n)!, 2))};

{a(n) = if( n<0, 0, subst(Pol(binary(n)), x ,1))};

{a(n) = if( n<1, 0, a(n\2) + n%2)}; /* Michael Somos, Mar 06 2004 */

a(n)=my(v=binary(n));sum(i=1,#v,v[i]) \\ Charles R Greathouse IV, Jun 24 2011

a(n)=norml2(binary(n)) \\ better use {A000120=hammingweight}. - M. F. Hasler, Oct 09 2012, edited Feb 27 2020

a(n)=hammingweight(n) \\ Michel Marcus, Oct 19 2013
(Common Lisp) (defun floor-to-power (n pow) (declare (fixnum pow)) (expt pow (floor (log n pow)))) (defun enabled-bits (n) (if (< n 4) (n-th n (list 0 1 1 2)) (+ (enabled-bits (floor (/ n (floor-to-power n 4)))) (enabled-bits (mod n (floor-to-power n 4)))))) ; Stephen K. Touset (stephen(AT)touset.org), Apr 04 2007

def A000120(n): return bin(n).count('1') # Chai Wah Wu, Sep 03 2014

import numpy as np
A000120 = np.array([0], dtype="uint8")
for bitrange in range(25): A000120 = np.append(A000120, np.add(A000120, 1))
print([A000120[n] for n in range(0, 105)]) # Karl-Heinz Hofmann, Nov 07 2022

def A000120(n): return n.bit_count() # Requires Python 3.10 or higher. - Pontus von Brömssen, Nov 08 2022

Python
```
# Also see links.
```

def A000120(n):
    if n <= 1: return Integer(n)
    return A000120(n//2) + n%2
[A000120(n) for n in range(105)]  # Peter Luschny, Nov 19 2012

def A000120(n) : return sum(n.digits(2)) # Eric M. Schmidt, Apr 26 2013

(0 to 127).map(Integer.bitCount()) // _Alonso del Arte, Mar 05 2019

a(0) = 0, a(2*n) = a(n), a(2*n+1) = a(n) + 1.
a(0) = 0, a(2^i) = 1; otherwise if n = 2^i + j with 0 < j < 2^i, a(n) = a(j) + 1.
G.f.: Product_{k >= 0} (1 + y*x^(2^k)) = Sum_{n >= 0} y^a(n)*x^n. - N. J. A. Sloane, Jun 04 2009
a(n) = a(n-1) + 1 - A007814(n) = log_2(A001316(n)) = 2n - A005187(n) = A070939(n) - A023416(n). - Henry Bottomley, Apr 04 2001; corrected by Ralf Stephan, Apr 15 2002
a(n) = log_2(A000984(n)/A001790(n)). - Benoit Cloitre, Oct 02 2002
For n > 0, a(n) = n - Sum_{k=1..n} A007814(k). - Benoit Cloitre, Oct 19 2002
a(n) = n - Sum_{k>=1} floor(n/2^k) = n - A011371(n). - Benoit Cloitre, Dec 19 2002
G.f.: (1/(1-x)) * Sum_{k>=0} x^(2^k)/(1+x^(2^k)). - Ralf Stephan, Apr 19 2003
a(0) = 0, a(n) = a(n - 2^floor(log_2(n))) + 1. Examples: a(6) = a(6 - 2^2) + 1 = a(2) + 1 = a(2 - 2^1) + 1 + 1 = a(0) + 2 = 2; a(101) = a(101 - 2^6) + 1 = a(37) + 1 = a(37 - 2^5) + 2 = a(5 - 2^2) + 3 = a(1 - 2^0) + 4 = a(0) + 4 = 4; a(6275) = a(6275 - 2^12) + 1 = a(2179 - 2^11) + 2 = a(131 - 2^7) + 3 = a(3 - 2^1) + 4 = a(1 - 2^0) + 5 = 5; a(4129) = a(4129 - 2^12) + 1 = a(33 - 2^5) + 2 = a(1 - 2^0) + 3 = 3. - Hieronymus Fischer, Jan 22 2006
A fixed point of the mapping 0 -> 01, 1 -> 12, 2 -> 23, 3 -> 34, 4 -> 45, ... With f(i) = floor(n/2^i), a(n) is the number of odd numbers in the sequence f(0), f(1), f(2), f(3), f(4), f(5), ... - Philippe Deléham, Jan 04 2004
When read mod 2 gives the Morse-Thue sequence A010060.
Let floor_pow4(n) denote n rounded down to the next power of four, floor_pow4(n) = 4 ^ floor(log4 n). Then a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2, a(n) = a(floor(n / floor_pow4(n))) + a(n % floor_pow4(n)). - Stephen K. Touset (stephen(AT)touset.org), Apr 04 2007
a(n) = n - Sum_{k=2..n} Sum_{j|n, j >= 2} (floor(log_2(j)) - floor(log_2(j-1))). - Hieronymus Fischer, Jun 18 2007
a(n) = A138530(n, 2) for n > 1. - Reinhard Zumkeller, Mar 26 2008
a(A077436(n)) = A159918(A077436(n)); a(A000290(n)) = A159918(n). - Reinhard Zumkeller, Apr 25 2009
a(n) = A063787(n) - A007814(n). - Gary W. Adamson, Jun 04 2009
a(n) = A007814(C(2n, n)) = 1 + A007814(C(2n-1, n)). - Vladimir Shevelev, Jul 20 2009
For odd m >= 1, a((4^m-1)/3) = a((2^m+1)/3) + (m-1)/2 (mod 2). - Vladimir Shevelev, Sep 03 2010
a(n) - a(n-1) = { 1 - a(n-1) if and only if A007814(n) = a(n-1), 1 if and only if A007814(n) = 0, -1 for all other A007814(n) }. - Brent Spillner (spillner(AT)acm.org), Sep 01 2010
a(A001317(n)) = 2^a(n). - Vladimir Shevelev, Oct 25 2010
a(n) = A139351(n) + A139352(n) = Sum_k {A030308(n, k)}. - Philippe Deléham, Oct 14 2011
From Hieronymus Fischer, Jun 10 2012: (Start)
a(n) = Sum_{j = 1..m+1} (floor(n/2^j + 1/2) - floor(n/2^j)), where m = floor(log_2(n)).
General formulas for the number of digits >= d in the base p representation of n, where 1 <= d < p: a(n) = Sum_{j = 1..m+1} (floor(n/p^j + (p-d)/p) - floor(n/p^j)), where m=floor(log_p(n)); g.f.: g(x) = (1/(1-x))*Sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)). (End)
a(n) = A213629(n, 1) for n > 0. - Reinhard Zumkeller, Jul 04 2012
a(n) = A240857(n,n). - Reinhard Zumkeller, Apr 14 2014
a(n) = log_2(C(2*n,n) - (C(2*n,n) AND C(2*n,n)-1)). - Gary Detlefs, Jul 10 2014
Sum_{n >= 1} a(n)/2n(2n+1) = (gamma + log(4/Pi))/2 = A344716, where gamma is Euler's constant A001620; see Sondow 2005, 2010 and Allouche, Shallit, Sondow 2007. - Jonathan Sondow, Mar 21 2015
For any integer base b >= 2, the sum of digits s_b(n) of expansion base b of n is the solution of this recurrence relation: s_b(n) = 0 if n = 0 and s_b(n) = s_b(floor(n/b)) + (n mod b). Thus, a(n) satisfies: a(n) = 0 if n = 0 and a(n) = a(floor(n/2)) + (n mod 2). This easily yields a(n) = Sum_{i = 0..floor(log_2(n))} (floor(n/2^i) mod 2). From that one can compute a(n) = n - Sum_{i = 1..floor(log_2(n))} floor(n/2^i). - Marek A. Suchenek, Mar 31 2016
Sum_{k>=1} a(k)/2^k = 2 * Sum_{k >= 0} 1/(2^(2^k)+1) = 2 * A051158. - Amiram Eldar, May 15 2020
Sum_{k>=1} a(k)/(k*(k+1)) = A016627 = log(4). - Bernard Schott, Sep 16 2020
a(m*(2^n-1)) >= n. Equality holds when 2^n-1 >= A000265(m), but also in some other cases, e.g., a(11*(2^2-1)) = 2 and a(19*(2^3-1)) = 3. - Pontus von Brömssen, Dec 13 2020
G.f.: A(x) satisfies A(x) = (1+x)*A(x^2) + x/(1-x^2). - Akshat Kumar, Nov 04 2023

A003714 Fibbinary numbers: if n = F(i1) + F(i2) + ... + F(ik) is the Zeckendorf representation of n (i.e., write n in Fibonacci number system) then a(n) = 2^(i1 - 2) + 2^(i2 - 2) + ... + 2^(ik - 2). Also numbers whose binary representation contains no two adjacent 1's.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20, 21, 32, 33, 34, 36, 37, 40, 41, 42, 64, 65, 66, 68, 69, 72, 73, 74, 80, 81, 82, 84, 85, 128, 129, 130, 132, 133, 136, 137, 138, 144, 145, 146, 148, 149, 160, 161, 162, 164, 165, 168, 169, 170, 256, 257, 258, 260, 261, 264

Offset: 0

N. J. A. Sloane

The name "Fibbinary" is due to Marc LeBrun.
"... integers whose binary representation contains no consecutive ones and noticed that the number of such numbers with n bits was fibonacci(n)". [posting to sci.math by Bob Jenkins (bob_jenkins(AT)burtleburtle.net), Jul 17 2002]
From Benoit Cloitre, Mar 08 2003: (Start)
A number m is in the sequence if and only if C(3m, m) (or equally, C(3m, 2m)) is odd.
a(n) == A003849(n) (mod 2). (End)
Numbers m such that m XOR 2*m = 3*m. - Reinhard Zumkeller, May 03 2005. [This implies that A003188(2*a(n)) = 3*a(n) holds for all n.]
Numbers whose base-2 representation contains no two adjacent ones. For example, m = 17 = 10001_2 belongs to the sequence, but m = 19 = 10011_2 does not. - Ctibor O. Zizka, May 13 2008
m is in the sequence if and only if the central Stirling number of the second kind S(2*m, m) = A007820(m) is odd. - O-Yeat Chan (math(AT)oyeat.com), Sep 03 2009
A000120(3*a(n)) = 2*A000120(a(n)); A002450 is a subsequence.
Every nonnegative integer can be expressed as the sum of two terms of this sequence. - Franklin T. Adams-Watters, Jun 11 2011
Subsequence of A213526. - Arkadiusz Wesolowski, Jun 20 2012
This is also the union of A215024 and A215025 - see the Comment in A014417. - N. J. A. Sloane, Aug 10 2012
The binary representation of each term m contains no two adjacent 1's, so we have (m XOR 2m XOR 3m) = 0, and thus a two-player Nim game with three heaps of (m, 2m, 3m) stones is a losing configuration for the first player. - V. Raman, Sep 17 2012
Positions of zeros in A014081. - John Keith, Mar 07 2022
These numbers are similar to Fibternary numbers A003726, Tribbinary numbers A060140 and Tribternary numbers. This sequence is a subsequence of Fibternary numbers A003726. The number of Fibbinary numbers less than any power of two is a Fibonacci number. We can generate this sequence recursively: start with 0 and 1; then, if x is in the sequence add 2x and 4x+1 to the sequence. The Fibbinary numbers have the property that the n-th Fibbinary number is even if the n-th term of the Fibonacci word is a. Respectively, the n-th Fibbinary number is odd (of the form 4x+1) if the n-th term of the Fibonacci word is b. Every number has a Fibbinary multiple. - Tanya Khovanova and PRIMES STEP Senior, Aug 30 2022
This is the ordered set S of numbers defined recursively by: 0 is in S; if x is in S, then 2*x and 4*x + 1 are in S. See Kimberling (2006) Example 3, in references below. - Harry Richman, Jan 31 2024

			From _Joerg Arndt_, Jun 11 2011: (Start)
In the following, dots are used for zeros in the binary representation:
  a(n)  binary(a(n))  n
    0:    .......     0
    1:    ......1     1
    2:    .....1.     2
    4:    ....1..     3
    5:    ....1.1     4
    8:    ...1...     5
    9:    ...1..1     6
   10:    ...1.1.     7
   16:    ..1....     8
   17:    ..1...1     9
   18:    ..1..1.    10
   20:    ..1.1..    11
   21:    ..1.1.1    12
   32:    .1.....    13
   33:    .1....1    14
   34:    .1...1.    15
   36:    .1..1..    16
   37:    .1..1.1    17
   40:    .1.1...    18
   41:    .1.1..1    19
   42:    .1.1.1.    20
   64:    1......    21
   65:    1.....1    22
(End)

Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Vol. 1, 2nd ed., Addison-Wesley, 1973, pp. 85, 493.

G. C. Greubel and T. D. Noe, Table of n, a(n) for n = 0..5000 (terms 0 to 1363 by T. D. Noe)
J.-P. Allouche, J. Shallit, and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math., Vol. 292, No. 1-3 (2005), pp. 1-15.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 74-77, pp. 754-756.
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
Marc Chamberland and Karl Dilcher, A Binomial Sum Related to Wolstenholme's Theorem, J. Number Theory, Vol. 171, Issue 11 (Nov. 2009), pp. 2659-2672. See Lemma 4.2 p. 2668.
O-Yeat Chan and Dante Manna, Divisibility properties of Stirling numbers of the second kind.
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
David Eppstein, Generating fibbinary numbers, three ways, 2021.
Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., Vol. 274, No. 1-3 (2004), pp. 147-160.
Roman S. Klyujkov, Quick Fibbinary Numbers Addition, C++ function with test program.
Ron Knott, Rabbit Sequence in Zeckendorf Expansion (A003714).
Linus Lindroos, Andrew Sills, and Hua Wang, Odd fibbinary numbers and the golden ratio, Fib. Q., Vol. 52, No. 1 (2014), pp. 61-65; alternative link.
A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See pages 1, 5.
Douglas M. McKenna, Fibbinary Zippers in a Monoid of Toroidal Hamiltonian Cycles that Generate Hilbert-Style Square-Filling Curves, ECA 2:2 (2022) Article S2R13.
Joris Nieuwveld, Fractions, Functions and Folding. A Novel Link between Continued Fractions, Mahler Functions and Paper Folding, Master's Thesis, arXiv:2108.11382 [math.NT], 2021.
Yaron Shany and Amit Berman, The Generating Idempotent Is a Minimum-Weight Codeword for Some Binary BCH Codes, arXiv:2408.08218 [cs.IT], 2024. See p. 10.
N. J. A. Sloane, Table of n, a(n) (base 10), a(n) (base 2), for n = 0..1000.
Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018.
Index entries for 2-automatic sequences.
Index entries for sequences defined by congruent products between domains N and GF(2)[X].
Index entries for sequences defined by congruent products under XOR.

A007088(a(n)) = A014417(n) (same sequence in binary). Complement: A004780. Char. function: A085357. Even terms: A022340, odd terms: A022341. First difference: A129761.
Other sequences based on similar restrictions on binary expansion: A003726 & A278038, A003754, A048715, A048718, A107907, A107909.
Cf. A000045, A005203, A005590, A007895, A037011, A048728, A048679, A056017, A060112, A072649, A083368, A089939, A106027, A106028, A116361.
3*a(n) is in A001969.
Cf. also A215022-A215025, A242407.
Cf. A014081 (count 11 bits).

import Data.Set (Set, singleton, insert, deleteFindMin)
a003714 n = a003714_list !! n
a003714_list = 0 : f (singleton 1) where
   f :: Set Integer -> [Integer]
   f s = m : (f $ insert (4*m + 1) $ insert (2*m) s')
         where (m, s') = deleteFindMin s
-- Reinhard Zumkeller, Jun 03 2012, Feb 07 2012

A003714 := proc(n)
    option remember;
    if n < 3 then
        n ;
    else
        2^(A072649(n)-1) + procname(n-combinat[fibonacci](1+A072649(n))) ;
    end if;
end proc:
seq(A003714(n),n=0..10) ;
# To produce a table giving n, a(n) (base 10), a(n) (base 2) - from N. J. A. Sloane, Sep 30 2018
# binary: binary representation of n, in human order
binary:=proc(n) local t1,L;
if n<0 then ERROR("n must be nonnegative"); fi;
if n=0 then return([0]); fi;
t1:=convert(n,base,2); L:=nops(t1);
[seq(t1[L+1-i],i=1..L)];
end;
for n from 0 to 100 do t1:=A003714(n); lprint(n, t1, binary(t1)); od:

fibBin[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k--]; FromDigits[fr, 2]]; Table[fibBin[n], {n, 0, 61}] (* Robert G. Wilson v, Sep 18 2004 *)
Select[Range[0, 270], ! MemberQ[Partition[IntegerDigits[#, 2], 2, 1], {1, 1}] &] (* Harvey P. Dale, Jul 17 2011 *)
Select[Range[256], BitAnd[#, 2 #] == 0 &] (* Alonso del Arte, Jun 18 2012 *)
With[{r = Range[10^5]}, Pick[r, BitAnd[r, 2 r], 0]] (* Eric W. Weisstein, Aug 18 2017 *)
Select[Range[0, 299], SequenceCount[IntegerDigits[#, 2], {1, 1}] == 0 &] (* Requires Mathematica version 10 or later. -- Harvey P. Dale, Dec 06 2018 *)

msb(n)=my(k=1); while(k<=n, k<<=1); k>>1
for(n=1,1e4,k=bitand(n,n<<1);if(k,n=bitor(n,msb(k)-1),print1(n", "))) \\ Charles R Greathouse IV, Jun 15 2011

select( is_A003714(n)=!bitand(n,n>>1), [0..266])
{(next_A003714(n,t)=while(t=bitand(n+=1,n<<1), n=bitor(n,1<A003714(t)) \\ M. F. Hasler, Nov 30 2021

for n in range(300):
    if 2*n & n == 0:
        print(n, end=",") # Alex Ratushnyak, Jun 21 2012

def A003714(n):
    tlist, s = [1,2], 0
    while tlist[-1]+tlist[-2] <= n:
        tlist.append(tlist[-1]+tlist[-2])
    for d in tlist[::-1]:
        s *= 2
        if d <= n:
            s += 1
            n -= d
    return s # Chai Wah Wu, Jun 14 2018

def fibbinary():
    x = 0
    while True:
        yield x
        y = ~(x >> 1)
        x = (x - y) & y # Falk Hüffner, Oct 23 2021
(C++)
/* start with x=0, then repeatedly call x=next_fibrep(x): */
ulong next_fibrep(ulong x)
{
    // 2 examples:         //  ex. 1             //  ex.2
    //                     // x == [*]0 010101   // x == [*]0 01010
    ulong y = x | (x>>1);  // y == [*]? 011111   // y == [*]? 01111
    ulong z = y + 1;       // z == [*]? 100000   // z == [*]? 10000
    z = z & -z;            // z == [0]0 100000   // z == [0]0 10000
    x ^= z;                // x == [*]0 110101   // x == [*]0 11010
    x &= ~(z-1);           // x == [*]0 100000   // x == [*]0 10000
    return x;
}
/* Joerg Arndt, Jun 22 2012 */

(0 to 255).filter(n => (n & 2 * n) == 0) // Alonso del Arte, Apr 12 2020
(C#)
public static bool IsFibbinaryNum(this int n) => ((n & (n >> 1)) == 0) ? true : false; // Frank Hollstein, Jul 07 2021

No two adjacent 1's in binary expansion.
Let f(x) := Sum_{n >= 0} x^Fibbinary(n). (This is the generating function of the characteristic function of this sequence.) Then f satisfies the functional equation f(x) = x*f(x^4) + f(x^2).
a(0) = 0, a(1) = 1, a(2) = 2, a(n) = 2^(A072649(n) - 1) + a(n - A000045(1 + A072649(n))). - Antti Karttunen
It appears that this sequence gives m such that A082759(3*m) is odd; or, probably equivalently, m such that A037011(3*m) = 1. - Benoit Cloitre, Jun 20 2003
If m is in the sequence then so are 2*m and 4*m + 1. - Henry Bottomley, Jan 11 2005
A116361(a(n)) <= 1. - Reinhard Zumkeller, Feb 04 2006
A085357(a(n)) = 1; A179821(a(n)) = a(n). - Reinhard Zumkeller, Jul 31 2010
a(n)/n^k is bounded (but does not tend to a limit), where k = 1.44... = A104287. - Charles R Greathouse IV, Sep 19 2012
a(n) = a(A193564(n+1))*2^(A003849(n) + 1) + A003849(n) for n > 0. - Daniel Starodubtsev, Aug 05 2021
There are Fibonacci(n+1) terms with up to n bits in this sequence. - Charles R Greathouse IV, Oct 22 2021
Sum_{n>=1} 1/a(n) = 3.704711752910469457886531055976801955909489488376627037756627135425780134020... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022

Edited by Antti Karttunen, Feb 21 2006
Cross reference to A007820 added (into O-Y.C. comment) by Jason Kimberley, Sep 14 2009
Typo corrected by Jeffrey Shallit, Sep 26 2014

A014417 Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary words starting with 1 not containing 11, with the word 0 added.

Original entry on oeis.org

0, 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101, 100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010, 1000000, 1000001, 1000010, 1000100, 1000101, 1001000, 1001001, 1001010, 1010000, 1010001, 1010010, 1010100, 1010101

Offset: 0

Olivier Gérard

Old name was: Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary vectors not containing 11.
For n > 0, write n = Sum_{i >= 2} eps(i) Fib_i where eps(i) = 0 or 1 and no 2 consecutive eps(i) can be 1 (see A035517); then a(n) is obtained by writing the eps(i) in reverse order.
"One of the most important properties of the Fibonacci numbers is the special way in which they can be used to represent integers. Let's write j >> k <==> j >= k+2. Then every positive integer has a unique representation of the form n = F_k1 + F_k2 + ... + F_kr, where k1 >> k2 >> ... >> kr >> 0. (This is 'Zeckendorf's theorem.') ... We can always find such a representation by using a "greedy" approach, choosing F_k1 to be the largest Fibonacci number =< n, then choosing F_k2 to be the largest that is =< n - F_k1 and so on. Fibonacci representation needs a few more bits because adjacent 1's are not permitted; but the two representations are analogous." [Concrete Math.]
Since the binary representation of n in base of Fibonacci numbers allows only the successive bit pairs 00, 01, 10 and leaves 11 unused, we can use a ternary representation using all trits 0, 1, 2 where 00 --> 0, 01 --> 1 and 10 --> 2 (e.g. binary 1001010 as ternary 1022). - Daniel Forgues, Nov 30 2009
The same sequence also arises when considering the NegaFibonacci representations of the integers, as follows. Take the NegaFibonacci representations of n = 0, 1, 2, ... (A215022) and of n = -1, -2, -3, ... (A215023), sort the union of these two lists into increasing binary order, and we get A014417. Likewise the corresponding list of decimal representations, A003714, is the union of A215024 and A215025 sorted into increasing order.  - N. J. A. Sloane, Aug 10 2012
Also, numbers, written in binary, such that no adjacent bits are equal to 1: A one-dimensional analog of the matrices considered in A228277/A228285, A228390, A228476, A228506 etc. - M. F. Hasler, Apr 27 2014
The sequence of final bits, starting with a(1), is the complement of the Fibonacci word A005614. - N. J. A. Sloane, Oct 03 2018
This representation is named after the Belgian Army doctor and mathematician Edouard Zeckendorf (1901-1983). - Amiram Eldar, Jun 11 2021

			The Zeckendorf expansions of 1, 2, ... are 1 = 1 = Fib_2 -> 1, 2 = 2 = Fib_3 -> 10, 3 = Fib_4 -> 100, 4 = 3+1 = Fib_4 + Fib_2 -> 101, 5 = 5 = Fib_5 -> 1000, 6 = 1+5 = Fib_2 + Fib_5 -> 1001, etc.

Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.
Donald E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.3, p. 169.
Edouard Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.

T. D. Noe and Harry J. Smith, Table of n, a(n) for n = 0..10000
Paul Dalenberg and Tom Edgar, Consecutive factorial base Niven numbers, Fibonacci Quart., Vol. 56, No. 2 (2018), pp. 163-166.
Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, 43 pages, no date, apparently unpublished. See Table 2.
Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, unpublished, no date. [Cached copy, with permission]
Donald E. Knuth, Fibonacci multiplication, Appl. Math. Lett., Vol. 1, No. 1 (1988), pp. 57-60.
Julien Leroy, Michel Rigo and Manon Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Mathematics, Vol. 340, No. 5 (2017), pp. 862-881.
Casey Mongoven, Zeckendorf Representations no. 17 (a musical composition with A014417).
Wikipedia, Zeckendorf's theorem.

Cf. A000045, A003794, A007895, A035517, A130234, A215022, A215023, A215024, A215025.
a(n) = A003714(n) converted to binary.
Cf. also A005614, A189920, A104324, A213911.
See A104326 for dual Zeckendorf representation of n.

a014417 0 = 0
a014417 n = foldl (\v z -> v * 10 + z) 0 $ a189920_row n
-- Reinhard Zumkeller, Mar 10 2013

A014417 := proc(n)
    local nshi,Z,i ;
    if n <= 1 then
        return n;
    end if;
    nshi := n ;
    Z := [] ;
    for i from A130234(n) to 2 by -1 do
        if nshi >= A000045(i) and nshi > 0 then
            Z := [1,op(Z)] ;
            nshi := nshi-A000045(i) ;
        else
            Z := [0,op(Z)] ;
        end if;
    end do:
    add( op(i,Z)*10^(i-1),i=1..nops(Z)) ;
end proc: # R. J. Mathar, Jan 31 2015

fb[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n * Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k-- ]; FromDigits[fr]]; Table[ fb[n], {n, 0, 30}] (* Robert G. Wilson v, May 15 2004 *)
r = Map[Fibonacci, Range[2, 12]]; Table[Total[FromDigits@ PadRight[{1}, Flatten@ #] &@ Reverse@ Position[r, #] & /@ Abs@ Differences@ NestWhileList[Function[k, k - SelectFirst[Reverse@ r, # < k &]], n + 1, # > 1 &]], {n, 0, 33}] (* Michael De Vlieger, Mar 27 2016, Version 10 *)
FromDigits/@Select[Tuples[{0,1},7],SequenceCount[#,{1,1}]==0&] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Aug 14 2019 *)

Zeckendorf(n)=my(k=0,v,m); while(fibonacci(k)<=n,k=k+1); m=k-1; v=vector(m-1); v[1]=1; n=n-fibonacci(k-1); while(n>0,k=0; while(fibonacci(k)<=n,k=k+1); v[m-k+2]=1; n=n-fibonacci(k-1)); v \\ Ralf Stephan

Zeckendorf(n)= { local(k); a=0; while(n>0, k=0; while(fibonacci(k)<=n, k=k+1); a=a+10^(k-3); n=n-fibonacci(k-1); ); a }
{ for (n=0, 10000, Zeckendorf(n); print(n," ",a); write("b014417.txt", n, " ", a) ) } \\ Harry J. Smith, Jan 17 2009

from sympy import fibonacci
def a(n):
    k=0
    x=0
    while n>0:
        k=0
        while fibonacci(k)<=n: k+=1
        x+=10**(k - 3)
        n-=fibonacci(k - 1)
    return x
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 07 2017, after PARI code by Harry J. Smith

Comment layout fixed by Daniel Forgues, Dec 07 2009
Typo corrected by Daniel Forgues, Mar 25 2010
Definition expanded and Duchene et al. reference added by N. J. A. Sloane, Aug 07 2018
Name corrected by Michel Dekking, Nov 30 2020

A001629 Self-convolution of Fibonacci numbers.

Original entry on oeis.org

0, 0, 1, 2, 5, 10, 20, 38, 71, 130, 235, 420, 744, 1308, 2285, 3970, 6865, 11822, 20284, 34690, 59155, 100610, 170711, 289032, 488400, 823800, 1387225, 2332418, 3916061, 6566290, 10996580, 18394910, 30737759, 51310978, 85573315, 142587180, 237387960, 394905492

Offset: 0

N. J. A. Sloane

Number of elements in all subsets of {1,2,...,n-1} with no consecutive integers. Example: a(5)=10 because the subsets of {1,2,3,4} that have no consecutive elements, i.e., {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, the total number of elements is 10. - Emeric Deutsch, Dec 10 2003
If g is either of the real solutions to x^2-x-1=0, g'=1-g is the other one and phi is any 2 X 2-matricial solution to the same equation, not of the form gI or g'I, then Sum'_{i+j=n-1} g^i phi^j = F_n + (A001629(n) - A001629(n-1)g')*(phi-g'I), where i,j >= 0, F_n is the n-th Fibonacci number and I is the 2 X 2 identity matrix... - Michele Dondi (blazar(AT)lcm.mi.infn.it), Apr 06 2004
Number of 3412-avoiding involutions containing exactly one subsequence of type 321.
Number of binary sequences of length n with exactly one pair of consecutive 1's. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Sep 02 2004
For this sequence the n-th term is given by (nF(n+1)-F(n)+nF(n-1))/5 where F(n) is the n-th Fibonacci number. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), Apr 20 2005
If an unbiased coin is tossed n times then there are 2^n possible strings of H and T. Out of these, number of strings with exactly one 'HH' is given by a(n) where a(n) denotes n-th term of this sequence. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), May 04 2005
a(n) is half the number of horizontal dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; a(n+1) = the number of vertical dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; thus 2*a(n)+a(n+1)=n*F(n+1) = the number of dominoes in all domino tilings of a 2 X n rectangle, where F=A000045, the Fibonacci sequence. - Roberto Tauraso, May 02 2005; Graeme McRae, Jun 02 2006
a(n+1) = (-i)^(n-1)*(d/dx)S(n,x)|A049310%20for%20the%20S-polynomials.%20-%20_Wolfdieter%20Lang">{x=i}, where i is the imaginary unit, n >= 1. First derivative of Chebyshev S-polynomials evaluated at x=i multiplied by (-i)^(n-1). See A049310 for the S-polynomials. - _Wolfdieter Lang, Apr 04 2007
For n >= 4, a(n) is the number of weak compositions of n-2 in which exactly one part is 0 and all other parts are either 1 or 2. - Milan Janjic, Jun 28 2010
For n greater than 1, a(n) equals the absolute value of (1 - (1/2 - i/2)*(1 + (-1)^(n + 1))) times the x-coefficient of the characteristic polynomial of the (n-1) X (n-1) tridiagonal matrix with i's along the main diagonal (i is the imaginary unit), 1's along the superdiagonal and the subdiagonal and 0's everywhere else (see Mathematica code below). - John M. Campbell, Jun 23 2011
For n > 0: a(n) = Sum_{k=1..n-1} (A039913(n-1,k)) / 2. - Reinhard Zumkeller, Oct 07 2012
The right-hand side of a binomial-coefficient identity [Gauthier]. - N. J. A. Sloane, Apr 09 2013
a(n) is the number of edges in the Fibonacci cube Gamma(n-1) (see the Klavzar 2005 reference, p. 149). Example: a(3)=2; indeed, the Fibonacci cube Gamma(2) is the path P(3) having 2 edges. - Emeric Deutsch, Aug 10 2014
a(n) is the number of c(i)'s, including repetitions, in p(n), where p(n)/q(n) is the n-th convergent p(n)/q(n) of the formal infinite continued fraction [c(0), c(1), ...]; e.g., the number of c(i)'s in p(3) = c(0)*c(1)*c(2)*c(3) + c(0)*c(1) + c(0)*c(3) + c(2)*c(3) + 1 is a(5) = 10. - Clark Kimberling, Dec 23 2015
Also the number of maximal and maximum cliques in the (n-1)-Fibonacci cube graph. - Eric W. Weisstein, Sep 07 2017
a(n+1) is the total number of fixed points in all permutations p on 1, 2, ..., n such that |k-p(k)| <= 1 for 1 <= k <= n. - Katharine Ahrens, Sep 03 2019
From Steven Finch, Mar 22 2020: (Start)
a(n+1) is the total binary weight (cf. A000120) of all A000045(n+2) binary sequences of length n not containing any adjacent 1's.
The only three 2-bitstrings without adjacent 1's are 00, 01 and 10. The bitsums of these are 0, 1 and 1. Adding these give a(3)=2.
The only five 3-bitstrings without adjacent 1's are 000, 001, 010, 100 and 101. The bitsums of these are 0, 1, 1, 1 and 2. Adding these give a(4)=5.
The only eight 4-bitstrings without adjacent 1's are 0000, 0001, 0010, 0100, 1000, 0101, 1010 and 1001. The bitsums of these are 0, 1, 1, 1, 1, 2, 2, and 2. Adding these give a(5)=10. (End)
Number of tilings of a 1 X n strip with monominoes (1 X 1 squares) and at least one domino (1 X 2 rectangles), where exactly one of the dominoes is colored gold. - Greg Dresden and Jiachen Weng, Jul 31 2025

			G.f. = x^2 + 2*x^3 + 5*x^4 + 10*x^5 + 20*x^6 + 38*x^7 + 71*x^8 + 130*x^9 + ... - _Michael Somos_, Jun 24 2018

Donald E. Knuth, Fundamental Algorithms, Addison-Wesley, 1968, p. 83, Eq. 1.2.8--(17). - Don Knuth, Feb 26 2019
Thomas Koshy, Fibonacci and Lucas Numbers with Applications, 2001, Chapter 15, page 187, "Hosoya's Triangle", and p. 375, eq. (32.13).
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989, p. 183, Nr.(98).

T. D. Noe, Table of n, a(n) for n = 0..500
Marco Abrate, Stefano Barbero, Umberto Cerruti and Nadir Murru, Colored compositions, Invert operator and elegant compositions with the "black tie", Discrete Math. 335 (2014), 1--7. MR3248794.
Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
Carlos Alirio Rico Acevedo and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci, Hypercubes and Isometric Words based on Swap and Mismatch Distance, arXiv:2303.09898 [math.CO], 2023.
Kassie Archer and Robert P. Laudone, Pattern avoidance and the fundamental bijection, arXiv:2407.06338 [math.CO], 2024. See p. 6.
Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar and Marko Petkovšek, Vertex and edge orbits of Fibonacci and Lucas cubes, arXiv:1407.4962 [math.CO], 2014. See Table 2.
Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar, et al., Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings, 2014.
Jean-Luc Baril, Sergey Kirgizov and Vincent Vajnovszki, Gray codes for Fibonacci q-decreasing words, arXiv:2010.09505 [cs.DM], 2020.
Daniel Birmajer, Juan Gil and Michael D. Weiner, Linear recurrence sequences and their convolutions via Bell polynomials, arXiv:1405.7727 [math.CO], 2014.
Daniel Birmajer, Juan B. Gil and Michael D. Weiner, Linear Recurrence Sequences and Their Convolutions via Bell Polynomials, Journal of Integer Sequences, 18 (2015), #15.1.2.
Matthew Blair, Rigoberto Flórez and Antara Mukherjee, Matrices in the Hosoya triangle, arXiv:1808.05278 [math.CO], 2018.
Matthew Blair, Rigoberto Flórez and Antara Mukherjee, Honeycombs in the Pascal triangle and beyond, arXiv:2203.13205 [math.HO], 2022. See p. 5.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Giuseppa Castiglione, Antonio Restivo and Marinella Sciortino, Circular Sturmian words and Hopcroft's algorithm, Theor. Comput. Sci. 410, No. 43, 4372-4381 (2009)
Charles H. Conley and Valentin Ovsienko, Shadows of rationals and irrationals: supersymmetric continued fractions and the super modular group, arXiv:2209.10426 [math-ph], 2022.
Éva Czabarka, Rigoberto Flórez and Leandro Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), #15.1.6.
Eric S. Egge, Restricted 3412-Avoiding Involutions, p. 16, arXiv:math/0307050 [math.CO], 2003.
Sergio Falcon, Half self-convolution of the k-Fibonacci sequence, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 96-106.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv:1203.6792 [math.CO], 2012.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
Rigoberto Flórez, Robinson Higuita and Alexander Ramírez, The resultant, the discriminant, and the derivative of generalized Fibonacci polynomials, arXiv:1808.01264 [math.NT], 2018.
Napoleon Gauthier (Proposer), Problem H-703, Fib. Quart., 50 (2012), 379-381.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
Martin Griffiths, Digit Proportions in Zeckendorf Representations, Fibonacci Quart. 48 (2010), no. 2, 168-174.
Verner E. Hoggatt, Jr. and M. Bicknell-Johnson, Fibonacci convolution sequences, Fib. Quart., 15 (1977), 117-122.
Milan Janjić, Hessenberg Matrices and Integer Sequences, J. Int. Seq. 13 (2010) # 10.7.8, section 3.
Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 8.
Sandi Klavžar, On median nature and enumerative properties of Fibonacci-like cubes, Disc. Math. 299 (2005), 145-153.
Sandi Klavžar, Structure of Fibonacci cubes: a survey, Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia; Preprint series Vol. 49 (2011), 1150 ISSN 2232-2094. (See Section 4.)
Toufik Mansour, Generalization of some identities involving the Fibonacci numbers, arXiv:math/0301157 [math.CO], 2003.
Toufik Mansour and Mark Shattuck, Pattern avoidance in flattened derangements, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
Pieter Moree, Convoluted convolved Fibonacci numbers, arXiv:math/0311205 [math.CO], 2003.
Pieter Moree, Convoluted Convolved Fibonacci Numbers, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.
László Németh, Walks on tiled boards, arXiv:2403.12159 [math.CO], 2024. See p. 2.
László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
Valentin Ovsienko, Shadow sequences of integers, from Fibonacci to Markov and back, arXiv:2111.02553 [math.CO], 2021.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Mihai Prunescu and Lorenzo Sauras-Altuzarra, On the representation of C-recursive integer sequences by arithmetic terms, arXiv:2405.04083 [math.LO], 2024. See p. 18.
Jeffrey B. Remmel and J. L. B. Tiefenbruck, Q-analogues of convolutions of Fibonacci numbers, Australasian Journal of Combinatorics, Volume 64(1) (2016), Pages 166-193.
J. Riordan, Notes to N. J. A. Sloane, Jul. 1968
Eric Weisstein's World of Mathematics, Edge Count
Eric Weisstein's World of Mathematics, Fibonacci Cube Graph
Eric Weisstein's World of Mathematics, Edge Count
Eric Weisstein's World of Mathematics, Maximal Clique
Eric Weisstein's World of Mathematics, Maximum Clique
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Row sums of triangles A058071, A134510, A134836.
First differences of A006478.
Cf. A000032, A000045, A001628, A010049, A037027, A055244, A214178.

List([0..40],n->Sum([0..n],k->Fibonacci(k)*Fibonacci(n-k))); # Muniru A Asiru, Jun 24 2018

a001629 n = a001629_list !! (n-1)
a001629_list = f [] $ tail a000045_list where
   f us (v:vs) = (sum $ zipWith (*) us a000045_list) : f (v:us) vs
-- Reinhard Zumkeller, Jan 18 2014, Oct 16 2011

I:=[0,0,1,2]; [n le 4 select I[n] else 2*Self(n-1)+Self(n-2)-2*Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Nov 19 2014

a:= n-> (<<2|1|0|0>, <1|0|1|0>, <-2|0|0|1>, <-1|0|0|0>>^n)[1,3]:
seq(a(n), n=0..40); # Alois P. Heinz, Aug 01 2008
# Alternative:
A001629 := n -> `if`(n<2, 0, (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4)):
seq(simplify(A001629(n)), n=0..37); # Peter Luschny, Apr 10 2018

Table[Sum[Binomial[n-i, i] i, {i, 0, n}], {n, 0, 34}] (* Geoffrey Critzer, May 04 2009 *)
Table[Abs[(1 -(1/2 -I/2)(1 - (-1)^n))*Coefficient[CharacteristicPolynomial[ Array[KroneckerDelta[#1, #2] I + KroneckerDelta[#1 + 1, #2] + KroneckerDelta[#1 -1, #2] &, {n-1, n-1}], x], x]], {n,2,50}] (* John M. Campbell, Jun 23 2011 *)
LinearRecurrence[{2,1,-2,-1}, {0,0,1,2}, 40] (* Harvey P. Dale, Aug 26 2013 *)
CoefficientList[Series[x^2/(1-x-x^2)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Nov 19 2014 *)
Table[(2nFibonacci[n-1] + (n-1)Fibonacci[n])/5, {n, 0, 40}] (* Vladimir Reshetnikov, May 08 2016 *)
Table[With[{fibs=Fibonacci[Range[n]]},ListConvolve[fibs,fibs]],{n,-1,40}]//Flatten (* Harvey P. Dale, Aug 19 2018 *)

Vec(1/(1-x-x^2)^2+O(x^99)) \\ Charles R Greathouse IV, Feb 03 2014

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -1,-2,1,2]^n)[2,4] \\ Charles R Greathouse IV, Jul 20 2016

def A001629(n): return (1/5)*(n*lucas_number2(n, 1, -1) - fibonacci(n))
[A001629(n) for n in (0..40)] # G. C. Greubel, Apr 06 2022

G.f.: x^2/(1 - x - x^2)^2. - Simon Plouffe in his 1992 dissertation
a(n) = A037027(n-1, 1), n >= 1 (Fibonacci convolution triangle).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4), n > 3.
a(n) = Sum_{k=0..n} A000045(k)*A000045(n-k).
a(n+1) = Sum_{i=0..F(n)} A007895(i), where F = A000045, the Fibonacci sequence. - Claude Lenormand (claude.lenormand(AT)free.fr), Feb 04 2001
a(n) = Sum_{k=0..floor(n/2)-1} (k+1)*binomial(n-k-1, k+1). - Emeric Deutsch, Nov 15 2001
a(n) = floor( (1/5)*(n - 1/sqrt(5))*phi^n + 1/2 ) where phi=(1+sqrt(5))/2 is the golden ratio. - Benoit Cloitre, Jan 05 2003
a(n) = a(n-1) + A010049(n-1) for n > 0. - Emeric Deutsch, Dec 10 2003
a(n) = Sum_{k=0..floor((n-2)/2)} (n-k-1)*binomial(n-k-2, k). - Paul Barry, Jan 25 2005
a(n) = ((n-1)*F(n) + 2*n*F(n-1))/5, F(n)=A000045(n) (see Vajda and Koshy reference).
F'(n, 1), the first derivative of the n-th Fibonacci polynomial evaluated at 1. - T. D. Noe, Jan 18 2006
a(n) = a(n-1) + a(n-2) + F(n-1), where F=A000045, the Fibonacci sequence. - Graeme McRae, Jun 02 2006
a(n) = (1/5)*(n-1/sqrt(5))*((1+sqrt(5))/2)^n + (1/5)*(n+1/sqrt(5))*((1-sqrt(5))/2)^n. - Graeme McRae, Jun 02 2006
a(n) = A055244(n-1) - F(n-2). Example: a(6) = 20 = A055244(5) - F(3) = (23 - 3). - Gary W. Adamson, Jul 27 2007
a(n) = term (1,3) in the 4 X 4 matrix [2,1,0,0; 1,0,1,0; -2,0,0,1; -1,0,0,0]^n. - Alois P. Heinz, Aug 01 2008
a(n) = A214178(n,1) for n > 0. - Reinhard Zumkeller, Jul 08 2012
a(n) = ((n+1)*F(n-1) + (n-1)*F(n+1))/5. - Richard R. Forberg, Aug 04 2014
(n-2)*a(n) - (n-1)*a(n-1) - n*a(n-2) = 0, n > 1. - Michael D. Weiner, Nov 18 2014
a(n) = Sum_{i=0..n-1} Sum_{j=0..i} F(j-1)*F(i-j), where F(n) = A000045 Fibonacci Numbers. - Carlos A. Rico A., Jul 14 2016
a(n) = (n*Lucas(n) - Fibonacci(n))/5, where Lucas = A000032, Fibonacci = A000045. - Vladimir Reshetnikov, Sep 27 2016
a(n) = (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4) for n >= 2. - Peter Luschny, Apr 10 2018
a(n) = -(-1)^n a(-n) for all n in Z. - Michael Somos, Jun 24 2018
E.g.f.: (1/50)*exp(-2*x/(1+sqrt(5)))*(2*sqrt(5)-5*(-1+sqrt(5))*x+exp(sqrt(5)*x)*(-2*sqrt(5)+5*(1+sqrt(5))*x)). - Stefano Spezia, Sep 03 2019
From Peter Bala, Jan 14 2025: (Start)
a(2*n+1) is even and a(2*n) has the same parity as Fibonacci(n).
For n >= 1, a(n) = (2/n)*Sum_{k = 0..n} k*Fibonacci(k)*Fibonacci(n-k). (End)

A027941 a(n) = Fibonacci(2*n + 1) - 1.

Original entry on oeis.org

0, 1, 4, 12, 33, 88, 232, 609, 1596, 4180, 10945, 28656, 75024, 196417, 514228, 1346268, 3524577, 9227464, 24157816, 63245985, 165580140, 433494436, 1134903169, 2971215072, 7778742048, 20365011073, 53316291172, 139583862444, 365435296161, 956722026040

Offset: 0

Clark Kimberling

Also T(2n+1,n+1), T given by A027935. Also first row of Inverse Stolarsky array.
Third diagonal of array defined by T(i, 1)=T(1, j)=1, T(i, j)=Max(T(i-1, j)+T(i-1, j-1); T(i-1, j-1)+T(i, j-1)). - Benoit Cloitre, Aug 05 2003
Number of Schroeder paths of length 2(n+1) having exactly one up step starting at an even height (a Schroeder path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis). Schroeder paths are counted by the large Schroeder numbers (A006318). Example: a(1)=4 because among the six Schroeder paths of length 4 only the paths (U)HD, (U)UDD, H(U)D, (U)DH have exactly one U step that starts at an even height (shown between parentheses). - Emeric Deutsch, Dec 19 2004
Also: smallest number not writeable as the sum of fewer than n positive Fibonacci numbers. E.g., a(5)=88 because it is the smallest number that needs at least 5 Fibonacci numbers: 88 = 55 + 21 + 8 + 3 + 1. - Johan Claes, Apr 19 2005 [corrected for offset and clarification by Mike Speciner, Sep 19 2023] In general, a(n) is the sum of n positive Fibonacci numbers as a(n) = Sum_{i=1..n} A000045(2*i). See A001076 when negative Fibonacci numbers can be included in the sum. - Mike Speciner, Sep 24 2023
Except for first term, numbers a(n) that set a new record in the number of Fibonacci numbers needed to sum up to n. Position of records in sequence A007895. - Ralf Stephan, May 15 2005
Successive extremal petal bends beta(n) = a(n-2). See the Ring Lemma of Rodin and Sullivan in K. Stephenson, Introduction to Circle Packing (Cambridge U. P., 2005), pp. 73-74 and 318-321. - David W. Cantrell (DWCantrell(AT)sigmaxi.net)
a(n+1)= AAB^(n)(1), n>=1, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 4=`110`, 12=`1100`, 33=`11000`, 88=`110000`, ..., in Wythoff code. AA(1)=1=a(1) but for uniqueness reason 1=A(1) in Wythoff code. - N. J. A. Sloane, Jun 29 2008
Start with n. Each n generates a sublist {n-1,n-1,n-2,..,1}. Each element of each sublist also generates a sublist. Add numbers in all terms. For example, 3->{2,2,1} and both 2->{1,1}, so a(3) = 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 = 12. - Jon Perry, Sep 01 2012
For n>0: smallest number such that the inner product of Zeckendorf binary representation and its reverse equals n: A216176(a(n)) = n, see also A189920. - Reinhard Zumkeller, Mar 10 2013
Also, numbers m such that 5*m*(m+2)+1 is a square. - Bruno Berselli, May 19 2014
Also, number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015
From Robert K. Moniot, Oct 04 2020: (Start)
Including a(-1):=0, consecutive terms (a(n-1),a(n))=(u,v) or (v,u) give all points on the hyperbola u^2-u+v^2-v-4*u*v=0 with both coordinates nonnegative integers.  Note that this follows from identifying (1,u+1,v+1) with the Markov triple (1,Fibonacci(2n-1),Fibonacci(2n+1)).  See A001519 (comments by Robert G. Wilson, Oct 05 2005, and Wolfdieter Lang, Jan 30 2015).
Let T(n) denote the n-th triangular number. If i, j are any two successive elements of the above sequence then (T(i-1) + T(j-1))/T(i+j-1) = 3/5. (End)

			a(5) = 88 = 2*33 + 12 + 4 + 1 + 5. a(6) = 232 = 2*88 + 33 + 12 + 4 + 1 + 6. - _Jon Perry_, Sep 01 2012
a(4) = 33 counts all nonempty submultisets of the last row: [1][2][3][4], [11][12][13][14][22][23][24][33][34], [111][112][113][122][123][124][133][134][222][223][233][234], [1111][1112][1122][1123][1222][1223][1233][1234]. - _Gus Wiseman_, Feb 10 2015

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 12.

T. D. Noe, Table of n, a(n) for n = 0..200
R. C. Alperin, A nonlinear recurrence and its relations to Chebyshev polynomials, Fib. Q., Vol. 58, No. 2 (2020), 140-142.
Russ Euler and Jawad Sadek, Problem B-912, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 39, No. 1 (2001), p. 85; From a Product to a Sum, Solution to Problem B-912 by Charles K. Cook, ibid., Vol. 39, No. 5 (2001), pp. 468-469.
Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 7.
Clark Kimberling, Interspersions.
Clark Kimberling, Interspersions and dispersions, Proceedings of the American Mathematical Society, 117 (1993) 313-321.
Ioana-Claudia Lazăr, Lucas sequences in t-uniform simplicial complexes, arXiv:1904.06555 [math.GR], 2019.
R. J. Mathar, Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings, arXiv:1311.6135 [math.CO], 2013, Table 60 (doubled).
Luis A. Medina and Armin Straub, On multiple and infinite log-concavity, Annals of Combinatorics, Vol. 20, No. 1 (2016), pp. 125-138; arXiv preprint, arXiv:1405.1765 [math.CO], 2014; preprint, 2014.
László Németh, Hyperbolic Pascal pyramid, arXiv:1511.02067 [math.CO], 2015 (2nd line of Table 1 is 3*a(n-2)).
László Németh, Pascal pyramid in the space H^2×R, arXiv:1701.06022 [math.CO], 2016. See bn in Table 1 p.10.
N. J. A. Sloane, Classic Sequences.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,-4,1).

Cf. A000045, A035507, A001906, A006318, A000032.
Related to partial sums of Fibonacci(k*n) over n: A000071, A099919, A058038, A138134, A053606; this sequence is the case k=2.
Cf. A212336 for more sequences with g.f. of the type 1/(1 - k*x + k*x^2 - x^3).
Cf. A000225 (sublist connection).
Cf. A258993 (row sums, n > 0), A000967.

a027941 = (subtract 1) . a000045 . (+ 1) . (* 2)
-- Reinhard Zumkeller, Mar 10 2013

[Fibonacci(2*n+1)-1: n in [0..30]]; // Vincenzo Librandi, Apr 18 2011

with(combinat): seq(fibonacci(2*n+1)-1,n=1..27); # Emeric Deutsch, Dec 19 2004
a:=n->sum(binomial(n+k+1,2*k), k=0..n): seq(a(n), n=-1..26); # Zerinvary Lajos, Oct 02 2007

Table[Fibonacci[2*n+1]-1,{n,0,17}] (* Vladimir Joseph Stephan Orlovsky, Jul 21 2008 *)
LinearRecurrence[{4,-4,1},{0,1,4},40] (* Harvey P. Dale, Aug 17 2021 *)

a(n):=sum(binomial(n+1,k+1)*fib(k),k,0,n); /* Vladimir Kruchinin, Oct 14 2016 */

a(n)=fibonacci(2*n+1)-1 \\ Charles R Greathouse IV, Nov 20 2012

concat(0, Vec(x/((1-x)*(1-3*x+x^2)) + O(x^40))) \\ Colin Barker, Jun 03 2016

a(n) = Sum_{i=1..n} binomial(n+i, n-i). - Benoit Cloitre, Oct 15 2002
G.f.: Sum_{k>=1} x^k/(1-x)^(2*k+1). - Benoit Cloitre, Apr 21 2003
a(n) = Sum_{k=1..n} F(2*k), i.e., partial sums of A001906. - Benoit Cloitre, Oct 27 2003
a(n) = Sum_{k=0..n-1} U(k, 3/2) = Sum_{k=0..n-1} S(k, 3), with S(k, 3) = A001906(k+1). - Paul Barry, Nov 14 2003
G.f.: x/((1-x)*(1-3*x+x^2)) = x/(1-4*x+4*x^2-x^3).
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3) with n>=2, a(-1)=0, a(0)=0, a(1)=1.
a(n) = 3*a(n-1) - a(n-2) + 1 with n>=1, a(-1)=0, a(0)=0.
a(n) = Sum_{k=1..n} F(k)*L(k), where L(k) = Lucas(k) = A000032(k) = F(k-1) + F(k+1). - Alexander Adamchuk, May 18 2007
a(n) = 2*a(n-1) + (Sum_{k=1..n-2} a(k)) + n. - Jon Perry, Sep 01 2012
Sum {n >= 1} 1/a(n) = 3 - phi, where phi = 1/2*(1 + sqrt(5)) is the golden ratio. The ratio of adjacent terms r(n) := a(n)/a(n-1) satisfies the recurrence r(n+1) = (4*r(n) - 1)/(r(n) + 1) for n >= 2. - Peter Bala, Dec 05 2013
a(n) = S(n, 3) - S(n-1, 3) - 1, n >= 0, with Chebyshev's S-polynomials (see A049310), where S(-1, x) = 0. - Wolfdieter Lang, Aug 28 2014
a(n) = -1 + (2^(-1-n)*((3-sqrt(5))^n*(-1+sqrt(5)) + (1+sqrt(5))*(3+sqrt(5))^n)) / sqrt(5). - Colin Barker, Jun 03 2016
E.g.f.: (sqrt(5)*sinh(sqrt(5)*x/2) + 5*cosh(sqrt(5)*x/2))*exp(3*x/2)/5 - exp(x). - Ilya Gutkovskiy, Jun 03 2016
a(n) = Sum_{k=0..n} binomial(n+1,k+1)*Fibonacci(k). - Vladimir Kruchinin, Oct 14 2016
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i+1,k-i). - Wesley Ivan Hurt, Sep 21 2017
a(n)*a(n-2) = a(n-1)*(a(n-1) - 1) for n>1. - Robert K. Moniot, Aug 23 2020
a(n) = Sum_{k=1..n} C(2*n-k,k). - Wesley Ivan Hurt, Dec 22 2020
a(n) = Sum_{k = 1..2*n+2} (-1)^k*Fibonacci(k). - Peter Bala, Nov 14 2021
a(n) = (2*cosh((1 + 2*n)*arccsch(2)))/sqrt(5) - 1. - Peter Luschny, Nov 21 2021
a(n) = F(n + (n mod 2)) * L(n+1 - (n mod 2)), where L(n) = A000032(n) and F(n) = A000045(n) (Euler and Sadek, 2001). - Amiram Eldar, Jan 13 2022

More terms from James Sellers, Sep 08 2000

Paul Barry's Nov 14 2003 formula, recurrences and g.f. corrected for offset 0 and index link for Chebyshev polynomials added by Wolfdieter Lang, Aug 28 2014

cp's OEIS Frontend

A000120 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Fortran

Haskell

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

PARI

Python

Python

Python

Python

SageMath

SageMath

Scala

Formula

A003714 Fibbinary numbers: if n = F(i1) + F(i2) + ... + F(ik) is the Zeckendorf representation of n (i.e., write n in Fibonacci number system) then a(n) = 2^(i1 - 2) + 2^(i2 - 2) + ... + 2^(ik - 2). Also numbers whose binary representation contains no two adjacent 1's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Python

Scala

Formula

Extensions

A014417 Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary words starting with 1 not containing 11, with the word 0 added.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Extensions

A001629 Self-convolution of Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

A328845 The first Fibonacci based variant of arithmetic derivative: a(p) = A000045(p) for prime p, a(uv) = a(u)v + u*a(v), with a(0) = a(1) = 0.