Is there a general procedure for inducing a formula / recognizing a pattern?

Question

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?

Answer 1

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)}$$

Answer 2

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)$$

Answer 3

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.\,$