Разделы 
Дополнительно
Задача по математике - 2897
2019-05-06 
Доказать, что каждое натуральное число либо является числом Фибоначчи (членом последовательности Фибоначчи), либо может быть представлено в виде суммы нескольких (различных) чисел Фибоначчи.
Решение:
Самое короткое решение этой задачи доставляет метод математической индукции. Условимся обозначать $k$-е число Фибоначчи, где $k = 1, 2, 3, \cdots$, через $u_k$. Предположим, что наше утверждение уже доказано для всех натуральных чисел $n$, меньших $k$-го числа Фибоначчи $u_k$ справедливость его для всех чисел, например, меньших $u_5 = 5$, легко проверить непосредственно. Ясно, что то же утверждение будет выполняться и для числа $u_k$. Далее, поскольку все числа между $u_k$ и $u_{k+1} = u_k + u_{k-1}$ представимы в виде $u_k + m$, где $0 < m < u_{k-1}$ и поскольку, по предположению индукции, все меньшие $u_{k-1}$ числа $m$ могут быть представлены в виде суммы каких-то различных чисел Фибоначчи, номера которых меньше $k-1$ 1, то число $n = u_k + m$ также представляется в виде суммы чисел Фибоначчи («старшее» из которых есть $u_k$. а номера остальных меньше $k-1$). Таким образом, мы установили, что наше предположение верно и для всех натуральных чисел, меньших $u_{k-1}$ откуда и вытекает его справедливость для всех натуральных чисел.
Доказать, что каждое натуральное число либо является числом Фибоначчи (членом последовательности Фибоначчи), либо может быть представлено в виде суммы нескольких (различных) чисел Фибоначчи.
Решение:
Самое короткое решение этой задачи доставляет метод математической индукции. Условимся обозначать $k$-е число Фибоначчи, где $k = 1, 2, 3, \cdots$, через $u_k$. Предположим, что наше утверждение уже доказано для всех натуральных чисел $n$, меньших $k$-го числа Фибоначчи $u_k$ справедливость его для всех чисел, например, меньших $u_5 = 5$, легко проверить непосредственно. Ясно, что то же утверждение будет выполняться и для числа $u_k$. Далее, поскольку все числа между $u_k$ и $u_{k+1} = u_k + u_{k-1}$ представимы в виде $u_k + m$, где $0 < m < u_{k-1}$ и поскольку, по предположению индукции, все меньшие $u_{k-1}$ числа $m$ могут быть представлены в виде суммы каких-то различных чисел Фибоначчи, номера которых меньше $k-1$ 1, то число $n = u_k + m$ также представляется в виде суммы чисел Фибоначчи («старшее» из которых есть $u_k$. а номера остальных меньше $k-1$). Таким образом, мы установили, что наше предположение верно и для всех натуральных чисел, меньших $u_{k-1}$ откуда и вытекает его справедливость для всех натуральных чисел.
