Year 12s: what will be the first way you research your future options? >>

Year 12s: what will be the first way you research your future options? >>

Year 12s: what will be the first way you research your future options? >>

Recurrence relation

Oh I Really Don't Care

Hey,

Just wondering if you can find a closed form for the following recurrence relation;

\displaystyle K_n = (n-1)(K_{n-1}+ K_{n-2})

With K_1 = 0 and K_1 =1

Oh I Really Don't Care

OP

For those who are itnerested,

\displaystyle K_n = n! \sum_{k=0}^{n} \frac{(-1)^n}{n!}

K0 = 0?

Oh I Really Don't Care

OP

oops

K0 = 1 cheers for the shout.

were u asked this somewhere

K1 = 0, right?

Oh I Really Don't Care

OP

Sorry again;

K1 = 0 and K0 = 1

Yes Ghosh, that should be a k!, not an n!

You're not going mad.

Oh I Really Don't Care

OP

And that n should be a k. Infact, here it is;

\displaystyle K_n = (n-1)(K_{n-1} + K_{n-2}) \; and \; K_1 = 0 \; and \; K_0 = 1

The closed form for the above recurrence is;

\displaystyle K_n = n! \left( \sum_{p=0}^{n} \frac{(-1)^p}{p!} \right)

How did you find the closed form?

Oh I Really Don't Care

OP

jj193

How did you find the closed form?

Spent about one hour trying different things (like comparing K(n) to n^n, 2^n, n!, blah, looking for a general pattern) and then proceeded to divide K(n) by them and K(n)/n! ~ 1/e.

We then note K(n) is always an integer so we consider the "best" approxiamtion to 1/e that when multiplied by n! gives us an integer - so clearly starting off with 1/e ~ sum[(-1)^k/k!] and proceeding from there would be a good idea. Then a rather straigtforward but book-keeping induction.

Just managed the induction :smile:

:smile:

thanks

Latest

Trending

Trending

Articles for you

Choosing the right housemates for second year of university

Choosing the right housemates for second year of university

A day in the life of a science student

A day in the life of a science student

What is an LLM and how could it benefit your career?

What is an LLM and how could it benefit your career?

Powerful questions business students forget to ask their career advisers

Powerful questions business students forget to ask their career advisers