User avatar
pathetic piss kitten @kitten@elizabeth.cat
5mo
what was the way to count the number of nodes in this kind of structure?
a tree of nodes, with a depth of 2
3
0
0
0
User avatar
pathetic piss kitten @kitten@elizabeth.cat
5mo
like, I know, by checking different depths, that the count is always (2^depth+1)-1

but that feels wrong ​:blobwtfnotlikethis:​
3
0
0
0
User avatar
anne_triangle 03.1 'Carbon' from the hit private key series 0x4 0x42 @1@mastodon.vierkantor.com
5mo
mx @kitten, true! we can prove this by induction on the depth.

for depth = 0, there is exactly one node, and 2^(0+1)-1 = 1. so the formula works in the base case.

now suppose we know it is true for all trees up to a given depth d. a tree with depth d+1 looks lik two trees of depth d connected by an additional node. so the number of nodes is two times the number of nodes in a tree of depth d, plus one. 2*(2^(d+1)-1) + 1 = 2*(2^(d+1)) - 2 - 1 = 2^((d+1)+1) - 1, showing that the formula holds for depth d+1 if it holds for depth d.

by induction, we conclude the formula is true for all depths ≥ 0.
1
0
1
0
User avatar
pathetic piss kitten @kitten@elizabeth.cat
5mo
@1 but it doesn't feel right ​:neocat_cry:​
2
0
1
0
User avatar
anne_triangle 03.1 'Carbon' from the hit private key series 0x4 0x42 @1@mastodon.vierkantor.com
5mo
mx @kitten, why not? the sum of a geometric sequence in base n is, up to accounting for starting and ending points, n to the power something.

another proof: let the sum S be equal to 1 + n + n^2 + ... + n^d. then nS = n + n^2 + ... + n^(d+1). so nS - S = n^(d+1) - 1. divide by n - 1 on both sides to get S = (n^(d+1) - 1) / (n - 1).

for n = 2, n - 1 = 2 - 1 = 1, so the sum is 2^(d+1) - 1, as we expected.
:neocat_think:1
0
0
0
1
User avatar
pathetic piss kitten @kitten@elizabeth.cat
5mo
@1 wait

no, it actually does feel right
0
0
1
0