Олимпиадные задачи из источника «параграф 3. Производящие функции»

Выведите формулу для чисел Каталана, воспользовавшись результатом задачи <a href="https://mirolimp.ru/tasks/161519">161519</a> и равенством   <img align="absmiddle" src="/storage/problem-media/61520/problem_61520_img_2.gif">   где

<img align="absmiddle" src="/storage/problem-media/61520/problem_61520_img_3.gif">   – обобщенные биномиальные коэффициенты.

Определение чисел Каталана можно найти в <a href="https://problems.ru/thes.php?%20letter=23#chisla_catalana">справочнике</a>.

Пусть   <img align="absmiddle" src="/storage/problem-media/61519/problem_61519_img_2.gif">   – производящая функция последовательности <i>чисел Каталана</i>. Докажите, что она удовлетворяет равенству <div align="CENTER"><i>C</i>(<i>x</i>) = <i>xC</i>²(<i>x</i>) + 1, </div>и получите явный вид функции<i>C</i>(<i>x</i>). Определение чисел Каталана можно найти в<a href="https://problems.ru/thes.php?letter=23#chisla_catalana">справочнике</a>.

Переменные<i>x</i>и<i>y</i>связаны равенством<div align="CENTER"> <i>x</i> = <i>y</i> + $\displaystyle {\frac{y^2}{2!}}$ + $\displaystyle {\frac{y^3}{3!}}$ +...+ $\displaystyle {\frac{y^n}{n!}}$ +... </div>Разложите<i>y</i>по степеням<i>x</i>.

Переменные<i>x</i>и<i>y</i>связаны равенством<div align="CENTER"> <i>x</i> = <i>y</i> + <i>y</i>² + <i>y</i>³ +...+ <i>y</i>ⁿ +... </div>Разложите<i>y</i>по степеням<i>x</i>.

Найдите общую формулу для коэффициентов ряда<div align="CENTER"> (1 - 4<i>x</i>)^{- $\scriptstyle {\textstyle\frac{1}{2}}$} = 1 + 2<i>x</i> + 6<i>x</i>² + 20<i>x</i>³ +...+ <i>a</i>_n<i>x</i>ⁿ +... </div>

Каков знак<i>n</i>-го члена в разложении произведения<div align="CENTER"> (1 - <i>a</i>)(1 - <i>b</i>)(1 - <i>c</i>)(1 - <i>d</i> )...= 1 - <i>a</i> - <i>b</i> + <i>ab</i> - <i>c</i> + <i>ac</i> + <i>bc</i> - <i>abc</i> - <i>d</i> +... </div>(<i>n</i>= 0, 1, 2,...)?

Определите коэффициент<i>a</i>_nв разложении<div align="CENTER"> (1 + <i>qx</i>)(1 + <i>qx</i>²)(1 + <i>qx</i>⁴)(1 + <i>qx</i>⁸)(1 + <i>qx</i>¹⁶)...= <i>a</i>₀ + <i>a</i>₁<i>x</i> + <i>a</i>₂<i>x</i>² + <i>a</i>₃<i>x</i>³ +... </div>

Придумайте какое-либо взаимно-однозначное соответствие между разбиениями натурального числа на различные и на нечётные слагаемые.

Обозначим через <i>d</i>(<i>n</i>) количество разбиений числа <i>n</i> на различные слагаемые, а через <i>l</i>(<i>n</i>) – на нечётные. Докажите равенства:   а)  <i>d</i>(0) + <i>d</i>(1)<i>x</i> + <i>d</i>(2)<i>x</i>² + ...  =  (1 + <i>x</i>)(1 + <i>x</i>²)(1 + <i>x</i>³)...;   б)  <i>l</i>(0) + <i>l</i>(1)<i>x</i> + <i>l</i>(2)<i>x</i>² + ...  =  (1 – <i>x</i>)^–1(1 – <i>x</i>³)^–1(1 – <i>x</i>⁵)^–1...;   в)  <i>d</i>(<i>n</i>)...

Докажите, что каждое натуральное число <i>n</i> может быть  2^<i>n</i>–1 – 1  различными способами представлено в виде суммы <i>меньших</i> натуральных слагаемых, если два представления, отличающихся хотя бы порядком слагаемых, считать различными.

На доске написано <i>n</i> натуральных чисел. Пусть <i>a_k</i> – количество тех из них, которые больше <i>k</i>. Исходные числа стерли и вместо них написали все положительные <i>a_k</i>. Докажите, что если с новыми числами сделать то же самое, то на доске окажется исходный набор чисел.

Например, для чисел 5, 3, 3, 2, получается следующая цепочка   (5, 3, 3, 2)  →  (4, 4, 3, 1, 1)  →  (5, 3, 3, 2).

Пусть <i>p</i>(<i>n</i>) – количество разбиений числа <i>n</i> (определение разбиений смотри <a href="https://problems.ru/thes.php?letter=16#Razbienia">здесь</a>). Докажите равенства:

<div align="center"><i>p</i>(0) + <i>p</i>(1)<i>x</i> + <i>p</i>(2)<i>x</i> '' + ...  =  (1 + <i>x</i> + <i>x</i>² + ...)...(1 + <i>x^k</i> + <i>x</i>^2<i>k</i> + ...)...  =  (1 – <i>x</i>)^–1(1 – <i>x</i>²)^–1(1 – <i>x</i>³)^–1... </div> (По определению сч...

Вычислите, используя производящие функции, следующие суммы:

а)   <img align="absmiddle" src="/storage/problem-media/61508/problem_61508_img_2.gif">    б)   <img align="absmiddle" src="/storage/problem-media/61508/problem_61508_img_3.gif">    в)   <img align="absmiddle" src="/storage/problem-media/61508/problem_61508_img_4.gif">    г)   <img align="absmiddle" src="/storage/problem-media/61508/problem_61508_img_5.gif">

Найдите производящие функции последовательностей многочленов Чебышева первого и второго рода:

<div align="center"><img src="/storage/problem-media/61507/problem_61507_img_2.gif"></div>Определения многочленов Чебышева можно найти в<a href="https://problems.ru/thes.php?letter=12#chebysheva">справочнике</a>.

Найдите производящие функции последовательности многочленов Фибоначчи  <i>F</i>(<i>x, z</i>) = <i>F</i>₀(<i>x</i>) + <i>F</i>₁(<i>x</i>)<i>z + F</i>₂(<i>x</i>)<i>z</i>² + ... + <i>F_n</i>(<i>x</i>)<i>zⁿ</i> + ...

и последовательности многочленов Люка   <i>L</i>(<i>x, z</i>) = <i>L</i>₀(<i>x</i>) + <i>L</i>₁(<i>x</i>)<i>z + L</i>₂(<i>x</i>)<i>z</i>² + ... + <...

Вычислите суммы а)$\sum\limits_{n=0}^{\infty}$${\dfrac{F_n}{2^n}}$;        б)$\sum\limits_{n=0}^{\infty}$${\dfrac{L_n}{2^n}}$. Здесь L_nобозначает числа Люка, смотри задачу<a href="https://mirolimp.ru/tasks/160585">3.133</a>.

а) Найдите производящую функцию последовательности чисел Люка (определение чисел Люка смотри в задаче <a href="https://mirolimp.ru/tasks/160585">160585</a>)б) Пользуясь этой функцией, выразите <i>L_n</i> через φ и <img width="15" height="30" align="MIDDLE" border="0" src="/storage/problem-media/61504/problem_61504_img_2.gif"> (см. задачу <a href="https://mirolimp.ru/tasks/161502">161502</a>).

Докажите, что бесконечная сумма<div align="CENTER"> <table> <tr valign="MIDDLE"><td align="RIGHT"> </td> <td align="LEFT">0, 1</td> </tr> <tr valign="MIDDLE"><td align="RIGHT">+</td> <td align="LEFT">0, 01</td> </tr> <tr valign="MIDDLE"><td align="RIGHT">+</td> <td align="LEFT">0, 002</td> </tr> <tr valign="MIDDLE"><td align="RIGHT">+</td> <td align="LEFT">0, 0003</td> </tr> <tr valign="MIDDLE"><td align="RIGHT">+</td> <td align="LEFT">0, 00005</td>...

а) Докажите, что производящая функция последовательности чисел Фибоначчи   <i>F</i>(<i>x</i>) = <i>F</i>₀ + <i>F</i>₁<i>x</i> + <i>F</i>₂<i>x</i>² + ... + <i>F_nxⁿ</i> + ... может быть записана в виде   <img align="absmiddle" src="/storage/problem-media/61502/problem_61502_img_2.gif">   где  <img width="15" height="28" align="MIDDLE" border="0" src="/storage/problem-media/61502/problem_61502_img_3.gif"> = <img width="41" height="41" align="MIDDLE" border="0" s...

Функции <i>a, b</i> и <i>c</i> заданы рядами     <img align="absmiddle" src="/storage/problem-media/61501/problem_61501_img_2.gif">     <img align="absmiddle" src="/storage/problem-media/61501/problem_61501_img_3.gif">     <img align="absmiddle" src="/storage/problem-media/61501/problem_61501_img_4.gif">Докажите, что  <i>a</i>³ +<i>b</i>³ +<i>c</i>³ – 3<i>abc</i>= (1 +<i>x</i>³)^<i>n</i>.

Назовем<i>экспонентой</i>следующий степенной ряд:

Exp(<i>z</i>)=1+<i>z</i>+<i>z</i>²/2!+...+<i>z</i>ⁿ/n!+... Докажите следующие свойства экспоненты: а)Exp$\nolimits{^\prime}$(<i>z</i>) = Exp$\nolimits$(<i>z</i>);    б)Exp$\nolimits$(($\alpha$+$\beta$)<i>z</i>) = Exp$\nolimits$($\alpha$<i>z</i>)^.Exp$\nolimits$($\beta$<i>z</i>).

Предположим, что у нас имеется 1000000 автобусных билетов с номерами от 000000 до 999999. Будем называть билет <i>счастливым</i>, если сумма первых трёх цифр его номера равна сумме трёх последних. Пусть <i>N</i> – количество счастливых билетов. Докажите равенства:

  а)  (1 + <i>x</i> + ... + <i>x</i>⁹)³(1 + <i>x</i>^–1 + ... + <i>x</i>^–9)³ = <i>x</i>²⁷ + ... + <i>a</i>₁<i>x</i> + <i>N</i> + <i>a</i>₁<i>x</i> + ... + <i>x</i>^–27;...

Вычислите производящие функции следующих последовательностей:

а)   <img align="absmiddle" src="/storage/problem-media/61497/problem_61497_img_2.gif">   б)   <img align="absmiddle" src="/storage/problem-media/61497/problem_61497_img_3.gif">

Докажите, что для всех неотрицательных <i>n</i> выполняются равенства   а)   <img align="absmiddle" src="/storage/problem-media/61496/problem_61496_img_2.gif">   б)   <img align="absmiddle" src="/storage/problem-media/61496/problem_61496_img_3.gif">

Докажите тождество:<div align="CENTER"> <table> <tr valign="MIDDLE"><td align="CENTER">(1 + <i>x</i> + <i>x</i>² +...+ <i>x</i>⁹)(1 + <i>x</i>¹⁰ + <i>x</i>²⁰ +...+ <i>x</i>⁹⁰)×</td> </tr> <tr valign="MIDDLE"><td align="CENTER">×(1 + <i>x</i>¹⁰⁰ + <i>x</i>²⁰⁰ +...+ <i>x</i>⁹⁰⁰)...= $\displaystyle {\dfrac{1}{1-x}}$.</td> </tr> </table> </div>