Solving for Levels in a Binary Lattice - Understanding Arithmetic Series

[rwinston]

Hi

I am currently working through the following issue: I am trying to read an list of values which contains the data points for a binomial lattice. If I have a list of N values that describes a binary tree, and I want to find out how many levels deep L the tree is, I can easily do it via the following method, since at each level, the number of nodes in the tree is 2^N-1:$$N=2^L-1$$

$$N+1=2^L$$

$$log_2{N}=L$$

So the number of nodes increases like: 1, 3, 7, 15, 31...But a binary lattice is different - the number of nodes increases like 1,3,6,10,15...i.e. it is an arithmetic sum:

$$N = \sum_{i=1}^L i$$

My issue is: given N, how can I solve for L?

Thanks!

 

[rwinston]

Got it, d'oh!

$$L = \frac{\sqrt{8N+1}-1}{2}$$

 

[tacman]

To solve for L, we can use the formula for the sum of an arithmetic series:

S = (n/2)(2a + (n-1)d)

Where:
S = sum of the series
n = number of terms
a = first term
d = common difference

In this case, n = L, a = 1, and d = 1. So we have:

N = (L/2)(2*1 + (L-1)*1)

N = (L/2)(L+1)

Solving for L, we get:

L^2 + L - 2N = 0

Using the quadratic formula, we get:

L = (-1 + √(1+8N))/2

Since we are dealing with a binary lattice, we can disregard the negative solution. So the final formula for finding L would be:

L = (-1 + √(1+8N))/2

Hope this helps!