exercise:0605c203bb: Difference between revisions
From Stochiki
(Created page with "<div class="d-none"><math> \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}</math></div> Let <math>b_k</math> denote the expected number of steps to reach <math>n</math> from <math>n-k</math>, in the process described in Exercise Exercise. <ul><li> Define <math>b_0 = 0</math>. Show that for <math>k > 0</mat...") |
No edit summary |
||
| Line 5: | Line 5: | ||
\newcommand{\secstoprocess}{\all} | \newcommand{\secstoprocess}{\all} | ||
\newcommand{\NA}{{\rm NA}} | \newcommand{\NA}{{\rm NA}} | ||
\newcommand{\mathds}{\mathbb}</math></div> Let <math>b_k</math> denote the expected number of steps to | \newcommand{\mathds}{\mathbb}</math></div> Let <math>b_k</math> denote the expected number of steps to reach <math>n</math> from <math>n-k</math>, in the process described in [[exercise:Fd190e1214 |Exercise]]. | ||
reach | |||
<math>n</math> from <math>n-k</math>, in the process described in | <ul style="list-style-type:lower-alpha"><li> | ||
<ul><li> | |||
Define <math>b_0 = 0</math>. Show that for <math>k > 0</math>, we have | Define <math>b_0 = 0</math>. Show that for <math>k > 0</math>, we have | ||
Latest revision as of 22:21, 15 June 2024
[math]
\newcommand{\NA}{{\rm NA}}
\newcommand{\mat}[1]{{\bf#1}}
\newcommand{\exref}[1]{\ref{##1}}
\newcommand{\secstoprocess}{\all}
\newcommand{\NA}{{\rm NA}}
\newcommand{\mathds}{\mathbb}[/math]
Let [math]b_k[/math] denote the expected number of steps to reach [math]n[/math] from [math]n-k[/math], in the process described in Exercise.
-
Define [math]b_0 = 0[/math]. Show that for [math]k \gt 0[/math], we have
[[math]] b_k = 1 + \frac 1k \bigl(b_{k-1} + b_{k-2} + \cdots + b_0\bigr)\ . [[/math]]
-
Let
[[math]] f(x) = b_0 + b_1 x + b_2 x^2 + \cdots\ . [[/math]]Using the recursion in part (a), show that [math]f(x)[/math] satisfies the differential equation[[math]] (1-x)^2 y' - (1-x) y - 1 = 0\ . [[/math]]
-
Show that the general solution of the differential equation in part (b) is
[[math]] y = \frac{-\log(1-x)}{1-x} + \frac c{1-x}\ , [[/math]]where [math]c[/math] is a constant.
-
Use part (c) to show that
[[math]] b_k = 1 + \frac 12 + \frac 13 + \cdots + \frac 1k\ . [[/math]]