3
$\begingroup$

Numbers of ways of representing a nonnegative integer as the ordered sum of odd numbers. For the first numbers we find that:

$0 \to 0\quad \text{ways}$

$1 \to 1\quad \text{way}$

$2: (1,1) \to 1\quad \text{ways}$

$3: (1,1,1), (3) \to 2\quad \text{ways}$

$4: (1,1,1,1), (3,1), (1,3)\to 3\quad \text{ways}$

$5: (1,1,1,1,1), (3,1,1), (1,3,1), (1,1,3), (5)\to 5\quad \text{ways}$

So, if $A_n$ is the numbers of ways to represent the nonnegative integer n as the ordered sum of $n$ (nonnegative) odd numbers, then $A_n = F_n$ where $F_n$ is the Fibonacci number.

How could this be proved?

I was trying to prove this by induction, but I'm having problems with the induction step. I really don't know what to do there.

$\endgroup$
8
$\begingroup$

EDIT: added the formal proof that the method described below works fine.

The base case has already been proven by you.

Now imagine all numbers up to $n-1$ can be written as you ask, in $a_{n-1}$ ways.

How can you write $n$? You can do one of two things:

You either take a way of writing $n-1$ and append a $1$ to its end, or you look at a way of writing $n-2$ and add $2$ to its last number. Because $a_{n-1}$ and $a_{n-2}$ take into consideration all permutations, it suffices to append the $1$ in the end and to sum the $2$ in the last position, therefore

$$a_n = a_{n-1} + a_{n-2}$$

We will make an example, showing that $a_6 = 8$.

We first append a $1$ to all the ways of writing 5:

$(1,1,1,1,1,1),(3,1,1,1),(1,3,1,1),(1,1,3,1),(5,1)$

And now add $2$ to the last entry in the ways of writing 4:

$(1,1,1,3),(3,3),(1,5)$

Therefore adding up to 8 different ways.

PROOF for the skeptical:

We shall use $(a_1, a_2, \cdots, a_k)$ as the notation for $\sum_{i=1}^{k} a_i$ Now assume that $(a_1, a_2, \cdots, a_k)$ is a way of writing $n$ as the sum of odd numbers. Then one of two things can happen:

  • $a_n = 1$
  • $a_n \ge 3$

Suppose $a_n = 1$. Then the sequece $(a_1, a_2, \cdots, a_{k-1})$ represents $n-1$. On the other hand, if $a_n \ge 3$ then the sequence $(a_1, a_2, \cdots, a_k-2)$ represents $n-2$. This means that for every sequence $(a_1, a_2, \cdots, a_k)$ you can uniquely connect it to, or a sequence for $n-1$, or a sequence for $n-2$. Since you can create these injections in both directions, you show that both sets of sequences have the same cardinality and therefore $a_n = a_{n-1} + a_{n-2}$.

$\endgroup$
  • $\begingroup$ You are adding the one to the end, right? Then you clearly have no doubles (in your example, adding the 1 at the beginning will not give all possibilities). $\endgroup$ – martini Nov 9 '16 at 10:01
  • $\begingroup$ @martini I am adding in the end, yes. I had written "beginning" and appended in the end, but I corrected that typo already. $\endgroup$ – RGS Nov 9 '16 at 10:03
  • 1
    $\begingroup$ Saw that, but you should remove "(or beginning)" or place another "(or first)" after "add 2". $\endgroup$ – martini Nov 9 '16 at 10:05
  • $\begingroup$ Thanks for answering. But I'm not quite gettting the part '' All in the beginning or all in the end''. What if to $a_{n-1}$ I append $1$ at the end and to $a_{n-1}$ add $2$ to the beggining? $\endgroup$ – Jazz Nov 9 '16 at 10:13
  • $\begingroup$ @RSerrao: I think if you just deleted those alternatives in parentheses, your answer would be clearer. $\endgroup$ – TonyK Nov 9 '16 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.