1
$\begingroup$

For some problems, it's pretty simple to deduce what a formula should look like after you enumerate a few examples, but for some problems, it's not so clear. For these less clear examples, is there some procedure I can follow to find the formula?

For example, just now, I was working on the problem:

Find the expected number of tosses it takes to get $k$ 6s in a row.

The recursive formula is

$$ E[N_k ] = 6(E[N_{k - 1}] + 1) $$

where $N_k$ is the number of tosses it takes to get $k$ 6s in a row. The initial condition is $E[N_1] = 6$ because $N_1$ is a geometric random variable with $1/6$ probability of success.

Then I enumerated a few cases:

$$ E[N_1] = 6 \\ E[N_2] = 42 \\ E[N_3] = 258 \\ E[N_4] = 1554 $$

It's not obvious to me what the formula should be. But I think it should look something like $$ E[N_k] = 6^k + (k - 1) * \text{something} + \text{maybe other terms} $$

But I don't know what this "something" and "maybe other terms" should be. If I sit here long enough I could probably figure it out, but is there some kind of general procedure that I can apply to a wide array of problems?

$\endgroup$
1
1
$\begingroup$

One good way is to try to convert this to a more standard linear recursion.

Letting $$a_n=6(a_{n-1}+1)=6a_{n-1}+6$$

We rewrite this as $$6=a_n-6a_{n-1}=a_{n-1}-6a_{n-2}$$

Whence $$a_n=6a_{n-1}+a_{n-1}-6a_{n-2}=7a_{n-1}-6a_{n-2}$$

and this can now be solved by standard means, yielding $$\boxed{a_n=\frac 65\times \left(6^n-1\right)}$$

$\endgroup$
8
  • $\begingroup$ What do you mean by 'standard means' here? $\endgroup$ – roulette01 Apr 17 at 20:22
  • 1
    $\begingroup$ It's a linear recursion, so you look at the characteristic polynomial $x^2-7x+6=(x-1)(x-6)$. Thus the solution is of the form $a_n=A6^n+B$ and then solve for $A,B$ using initial values. $\endgroup$ – lulu Apr 17 at 20:23
  • $\begingroup$ Ah I see. I've never formally learned recursion. My understanding is there are a lot of analogies between how recursive formulas are solved vs. how ODEs are solved, and this general solution seems to be analogous to formulas in second order ODEs. $\endgroup$ – roulette01 Apr 17 at 20:25
  • $\begingroup$ If you were to solve this problem without recursion, and by just inspecting the first several enumerations, is there a general approach to guess what that formula should be? $\endgroup$ – roulette01 Apr 17 at 20:26
  • $\begingroup$ I think guessing is hard. You could guess that $a_n=A6^n+p(n)$ where $p(n) $ is a low degree polynomial...but I don't know how reliable that sort of guesswork is. Works in this case, though. $\endgroup$ – lulu Apr 17 at 20:28
0
$\begingroup$

If you call $a_k=E[N_k]$ then you end up with a linear induction relation: $$a_k-6a_{k-1}=6$$

Since it is linear, it solves as the sum of general solution of homegenous equation $H_k-6H_{k-1}=0$, which is $H_k=6^kH_0$ and one particular solution of the full equation.

The theory says that if the RHS is of the form $P(k)r^k$ then you can find a particular solution of the form $Q(k)r^k$ with $\deg(Q)=\deg(P)+m$ where $m$ is the multiplicity of the root of the homogenous equation.

In this case $RHS = 6\times 1^k$ and the single root of homogenous equation is $r=6$. So the multiplicity of $1$ is just $m=0$ (i.e. not a root) this means $\deg(Q)=0+0=0$.

All that to say that our particular solution is simply a constant...

Therefore let search for $S_k=c$ then $c-6c=6\iff c=-\frac 65$

Our general solution is then $$a_k=H_k+S_k=6^kH_0-\frac 65$$

We now solve for initial conditions:

$a_1=6=6H_0-\frac 65\iff H_0=\frac 65$ and we get $$E[N_k]=\frac 65(6^k-1)$$

$\endgroup$
1
0
$\begingroup$

You asked

is there some kind of general procedure that I can apply to a wide array of problems?

Around 1960 there was some work on a General Problem Solver which had very limited capabilities but much progress has been made since 1960. Still, there is no way to solve all problems and probably never will be.

However, the solution of linear recurrences is known for a long time. For example, $$a_n=6(a_{n-1}+1)=6a_{n-1}+6$$ is easily solved using the theory.

For this particular difference equation with initial value $\,a_1\!=\!6\,$ a lookup of $\,6,42,258,1554\,$ in OEIS returns OEIS sequence A105281 "a(0)=0; a(n)=6*a(n-1)+6." This entry has a program

(PARI) a(n)=if(n<0, 0, (6^n-1)*6/5)

which gives a formula for the solution.

The Mathematica program has a function RSolve which solves recurrences and also has limited capabilities

You can use the Mathematica (or WolframAlpha) command

RSolve[a[n] == 6 a[n - 1] + 6 && a[1] == 6, a[n], n]

to get the particular solution $\,a_n = 6 (6^n-1)/5.\,$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.