Question

Линейные рекуррентные соотношения первого порядка с переменным коэффициентом. К числу, первоначально равному нулю, прибавляется шаг за шагом по единице до получения значения , . Докажите, что при этом потребуется переносов единицы в старший разряд.

Answer 1

Для доказательства можно использовать индук­цию.
Но формулу 2^n - n - 1 можно вывести, исходя лишь из условия задачи. Обозначим через S(n) исследуемое количество переносов и за­метим, что если прибавлением единиц уже получено число 2^n-1 - 1 (на это потребуется S(n-l) переносов), то очередное прибавление единицы потребует n - 1 переносов и приведет к числу 2^n-1, двоич­ная запись которого есть 10...0 (количество нулей после единицы равно n-1).

Далее в процессе достижения числа 11...1 (n единиц) потребуется еще S(n-l) переносов. Получаем рекуррентное уравне­ние S(n) = 2S(n - 1) + n - 1 или


S(n)-2S(n-l) = n-l, (1)

при этом s(0) = 0.

Характеристическое уравнение, соответствующее рекуррентному уравнению (1), имеет вид А - 2 = 0. Общее реше­ние однородного уравнения S(n) - 2S(n - 1) = 0 есть сТ.
Правую часть уравнения (1) можно записать в виде квазиполинома (n-1)*n. Значение 1 не является корнем характеристического уравнения, поэтому (ур. 1) обладает частным решением вида an + X; подставляя это выражение вместо s(n) в (1), получаем an + X - 2(а(n - 1) + X) = n - 1, и, приравнивая в левой и правой частях коэффициенты при первой и нулевой степенях n, имеем а = X = -1. Получаем общее ре­шение уравнения (1): S(n) = C2^n- n- 1. Подбираем значение кон­станты стак, чтобы выполнялось S(0) = 0; для этого должно выпол­няться C •2 - 2 = 0, т. е. C= 1. Итак, потребуется 2^n- n- 1 переносов единиц в старшие разряды.

Answer 2

Для доказательства этого утверждения рассмотрим линейное рекуррентное соотношение первого порядка с переменным коэффициентом вида:

$a_{n+1} = c_n a_n + d_n,$

где $c_n$ и $d_n$ - переменные коэффициенты, $a_0 = 0$ и $a_N = M$.

Мы знаем, что $a_0 = 0$, поэтому первый член последовательности равен нулю:

$a_1 = c_0 a_0 + d_0 = d_0.$

Далее, используя рекуррентное соотношение, можем выразить следующий член последовательности:

$a_2 = c_1 a_1 + d_1 = c_1 d_0 + d_1.$

Продолжая этот процесс, получим:

$\begin{aligned} a_3 &= c_2 a_2 + d_2 = c_2(c_1 d_0 + d_1) + d_2 \\ &= c_2 c_1 d_0 + c_2 d_1 + d_2 \end{aligned}$

$\begin{aligned} a_4 &= c_3 a_3 + d_3 = c_3(c_2 c_1 d_0 + c_2 d_1 + d_2) + d_3 \\ &= c_3 c_2 c_1 d_0 + c_3 c_2 d_1 + c_3 d_2 + d_3 \end{aligned}$

Продолжая этот процесс до $a_N$, мы получим выражение для $a_N$ в виде суммы произведений переменных коэффициентов и начальных значений:

$a_N = c_{N-1}c_{N-2}\cdots c_1 d_0 + c_{N-1}c_{N-2}\cdots c_2 d_1 + \cdots + c_{N-1} d_{N-2} + d_{N-1}$

Так как все коэффициенты $c_n$ и $d_n$ равны единице, кроме первых двух, можно заменить каждый $c_n$ на единицу. Тогда выражение для $a_N$ принимает вид:

$a_N = d_0 + d_1 + \cdots + d_{N-1}$

Таким образом, для того, чтобы вычислить значение $a_N$, нужно выполнить $N$ сложений. Поскольку $N$ - это число шагов, за которые $a$ увеличивается на единицу от $0$ до $M$, мы можем заключить, что для выполнения каждого шага необходимо выполнить одно сложение, требующее переноса единицы в старший разряд. Всего необходимо выполнить $N$ шагов, поэтому пот