Ordered "sums" of natural number k using natural number addends no smaller than 2 Using natural numbers no smaller than 2, we can express the number 3 as one ordered "sum": 3, and we can express the number 6 as 5 ordered "sums": 6 = 4 + 2 = 3 + 3 = 2 + 4 = 2 + 2 + 2.
In how many ways can the number k be expressed as an ordered "sum" with natural number addends no smaller than 2?
 A: For $k$ a positive integer, let $a_k$ denote the number of ways to express $k$ as an ordered sum of integers no smaller than $2$.
If $k\ge3$, then the number of such expressions with first term equal to $2$ is $a_{k-2}$ (deleting the first term is a bijection), and the number of such expressions with first term greater than $2$ is $a_{k-1}$ (subtracting $1$ from the first term is a bijection). Hence the numbers $a_k$ satisfy the Fibonacci recurrence $a_k=a_{k-1}+a_{k-2}$ for $k\ge3$. Since $a_1=0=F_0$ and $a_2=1=F_1$, it follows that $a_k$ is equal to the Fibonacci number $F_{k-1}$ for all $k\ge3$.
P.S. I have been asked to esplain those bijections in greater detail.
For $k\in\mathbb N$ let $A_k$ be the set of all integer sequences $(x_1,\dots,x_m)$ (of any length $m\le n/2$) such that $x_i\ge2$ for each $i$ and $x_1+\cdots+x_m=k$. Thus $a_k=|A_k|$. Let $B_k=\{(x_1,\dots,x_m)\in A_k:x_1=2\}$ and let $C_k=\{(x_1,\dots,x_m)\in A_k:x_1\gt2\}$. Let $b_k=|B_k|$ and $c_k=|C_k|$; then $a_k=b_k+c_k$, since $B_k\cap C_k=\emptyset$ and $B_k\cup C_k=A_k$.
Claim 1. $b_k=a_{k-2}$ for $k\ge3$.
Proof. Define a bijection $f:B_k\to A_{k-2}$ by setting $f(x_1,x_2,\dots,x_m)=(x_2,\dots,x_m)$.
Claim 2. $c_k=a_{k-1}$ for $k\ge3$.
Proof. Define a bijection $g:C_k\to A_{k-1}$ by setting $g(x_1,x_2,\dots,x_m)=(x_1-1,x_2,\dots,x_m)$.
It follows that, for $k\ge3$, we have
$$a_k=b_k+c_k=a_{k-2}+a_{k-1}.$$
Example. $k=7$, $a_7=8=5+3=a_6+a_5$:
$(7)\mapsto(6)$
$(5,2)\mapsto(4,2)$
$(4,3)\mapsto(3,3)$
$(3,4)\mapsto(2,4)$
$(3,2,2)\mapsto(2,2,2)$
$(2,5)\mapsto(5)$
$(2,3,2)\mapsto(3,2)$
$(2,2,3)\mapsto(2,3)$
