Online Course Discussion Forum
math challenge II-A combinatorics 7.21
I don't understand what the problem is asking. What does a0=1,an+1=∑k=0naka0=1,an+1=∑k=0nak. mean?na
I think for both this question and 7.30 it's good to review "summation notation" which is also called "signma notation" for the Greek letter sigma: $\Sigma$.
For a sequence $a_j$, the notation just means to add up terms of the sequence, starting with the term on the bottom and ending with the term on the top: $$\sum_{j=1}^N a_j = a_1 + a_2 + a_3 + \cdots + a_N.$$Thus it is a more formal way of writing things without using the ... notation. As another quick example, $$\sum_{j=1}^8 j^2 = 1^2 + 2^2 + \cdots + 8^2 = 204.$$
In 7.21 we are defining a recursive sequence using this notation, for example, $a_2 = a_0 + a_1$.
In 7.30 we want to show that the sum of the first n Fibonacci numbers is equal to the (n+2)nd number - 1. You'll want to use similar ideas as to 7.8, so if needed it's good to write out lots of examples and see how they relate.
Thanks, but for 7.21, why is the sequence 1,1,2,4,8, etc. ? The question didn't ask about the power of 2. Besides, why is there two 1s at the start?
For 7.21, we need to just follow the recursive definition for the sequence. We are given $a_0 = 1$. Then ever previous term (according to the recursive definition) is the sum of all the previous terms: $$\begin{aligned} a_1 &= a_0 = 1 \\ a_2 &= a_0 + a_1 = 1 + 1 = 2 \\ a_3 &= a_0 + a_1 + a_2 = 1 + 1 + 2 = 4 \\ a_4 &= \ldots \end{aligned}$$ From this, we start seeing the pattern that actually all the later terms all are powers of 2.
Social networks