A112088 Number of leaf nodes in a binary tree.

2, 3, 5, 7, 11, 16, 24, 36, 54, 81, 122, 183, 274, 411, 617, 925, 1388, 2082, 3123, 4684, 7026, 10539, 15809, 23713, 35570, 53355, 80032, 120048, 180072, 270108, 405162, 607743, 911615, 1367422, 2051133, 3076700, 4615050, 6922575, 10383862

Offset: 1

Author

Simon Strandgaard, Nov 29 2005

Keywords

• easy
• nonn

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..5678 (terms 1..1000 from David W. Wilson)
• Simon Strandgaard, About this sequence

Programs

Maple

a:=2;b:=0;c:=4;p := proc() local x; global a,b,c; x := b + a; c := c - x; if(c<0) then a := a*2; c := c + a*2; end if; b := floor((a*2-c+1) / 2); x end proc: seq(p(), i=0..40);

Mathematica

f[n_] := Block[{a = 2, b = 0, c = 4}, Do[x = b + a; c -= x; If[c < 0, a *= 2; c += 2a]; b = Floor[(2a - c + 1)/2], {i, n}]; x]; Array[f, 40] (* Robert G. Wilson v, Jan 11 2006 *)
f[s_] := Append[s, Ceiling[2 + Plus @@ s/2]]; Nest[f, {2}, 38] (* Robert G. Wilson v, Jul 08 2006 *)

PARI

first(n)=my(v=vector(n),s); v[1]=s=2; for(n=2,n, s+=v[n]=(s+5)\2); v \\ Charles R Greathouse IV, Nov 07 2016

Ruby

a,c=2,4;p Array.new(99){c-=x=(a*4-c+1)/2;c+=2*a*=2 if c<0;x}

Formula

a(1)=2; a(n) = floor((5 + Sum_{j=1..n-1} a(j))/2). - Graeme McRae, Jun 09 2006

a(n) ~ c * 3^n / 2^n, where c = 1.4086393347913639409553312264320529315790457870253974319560288484955... - Vaclav Kotesovec, Dec 26 2023