Question 4
A tree branches as follows: after growing for one year it begins to branch; thereafter, every two years it produces another branch. This rule also applies to every new branch: one year after it appears it produces a child branch, and that main branch then produces another branch every two years. Count the main trunk as a special branch. Find the number of branches during the fifth year.
Let $S_n$ be the number of branches during year $n$. Prove
$$S_n=S_{n-1}+S_{n-2}.$$
Let $a\gt b$ satisfy $a+b=1$, $ab=-1$. Prove by induction that
$$S_n=\frac1{\sqrt5}(a^{n+1}-b^{n+1}).$$
Indexing clarification: as required by the displayed formula, the first year contains just the trunk ($S_1=1$); the first new branch appears at its end, so $S_2=2$.
Let $S_n$ be the number of branches during year $n$. Prove
$$S_n=S_{n-1}+S_{n-2}.$$
Let $a\gt b$ satisfy $a+b=1$, $ab=-1$. Prove by induction that
$$S_n=\frac1{\sqrt5}(a^{n+1}-b^{n+1}).$$
Indexing clarification: as required by the displayed formula, the first year contains just the trunk ($S_1=1$); the first new branch appears at its end, so $S_2=2$.