You're planting a tree, which sprouts 2 leaves on day 1. Each day, the tree branches out, doubling the number of leaves, but from day 2 on, you will trim one of the branches out, ceasing the leaves to grow on that branch. The number of leaves consequently runs as the day passes by as shown above.
On day 17, how many leaves will this tree have?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let S n denote the number of leaves on n th day.
We know, S n = 2 S n − 1 − 1
Using Recurrence Relation, S n − 2 S n − 1 ⇒ S n = − 1 = c 2 n + 1 − 2 − 1 = c 2 n + 1
Also, S 1 = 2 ⇒ c = c ⋅ 2 1 + 1 = 2 1
Thus on 17 th day, number of leaves will be S 1 7 = 2 1 6 + 1 = 6 5 5 3 7
Problem Loading...
Note Loading...
Set Loading...
This tree branching of leaves is, in fact, an inverted version of Pascal's triangle, and with the condition of snipping one branch out everyday, the triangle will be adjusted as shown below:
As we can see, the number 1 on the far left can contribute only 1 new leaf to the right original Pascal's triangle due to the line is cut out (as the tree branch is trimmed). Therefore, from the first level, there are 1+1 leaves, and on the next level, the number of leaves will run as 2 n − 1 + 1 for any n t h level (day n). For example, on day 3, there will be 2 3 − 1 +1 = 4+1 = 5.
Hence, on day 17, there will be 2 1 7 − 1 +1 = 65537 leaves.