5
$\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$
0

1 Answer 1

9
$\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$
9
  • $\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
    Commented Nov 9, 2016 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
    Commented Nov 9, 2016 at 10:03
  • 1
    $\begingroup$ Saw that, but you should remove "(or beginning)" or place another "(or first)" after "add 2". $\endgroup$
    – martini
    Commented Nov 9, 2016 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$
    – asd
    Commented Nov 9, 2016 at 10:13
  • $\begingroup$ @RSerrao: I think if you just deleted those alternatives in parentheses, your answer would be clearer. $\endgroup$
    – TonyK
    Commented Nov 9, 2016 at 13:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .