Combinatorial Numbers

Let there be a recurrence relation Pa(n)=nPa(n1)+an{ P }_{ a }\left( n \right) =n\cdot { P }_{ a }\left( n-1 \right) +{ a }^{ n } , where Pa(0)=1{ P }_{ a }\left( 0 \right) =1. Show that Pa(n)ean!{ P }_{ a }\left( n \right) \sim { e }^{ a }n! for large nn.

Solution

We first show that the above recurrence relation constructs the sum Pa(n)=n!(k=0nakk!).{P}_{a}(n) = n!\left( \sum _{ k=0 }^{ n }{ \frac { { a }^{ k } }{ k! } } \right).

Now we prove by induction.

When k=1k=1

1!(a00!+a11!)=1(1)+a1! \left(\frac{{a}^{0}}{0!} + \frac{{a}^{1}}{1!}\right) = 1(1)+a

1!(k=01akk!)=1Pa(0)+a1=Pa(1).1!\left( \sum _{ k=0 }^{ 1 }{ \frac { { a }^{ k } }{ k! } } \right) = 1\cdot {P}_{a}(0) + {a}^{1} = {P}_{a}(1).

When k=nk=n

n!(a00!+a11!+...+ann!)=n(n1)!(a00!+a11!+...+an1(n1)!)+ann! \left(\frac{{a}^{0}}{0!} + \frac{{a}^{1}}{1!} + ...+ \frac{{a}^{n}}{n!}\right) = n(n-1)! \left(\frac{{a}^{0}}{0!} + \frac{{a}^{1}}{1!} + ...+ \frac{{a}^{n-1}}{(n-1)!}\right) + {a}^{n}

n!(k=0nakk!)=nPa(n1)+an1=Pa(n).n!\left( \sum _{ k=0 }^{ n }{ \frac { { a }^{ k } }{ k! } } \right) = n\cdot {P}_{a}(n-1) + {a}^{n-1} = {P}_{a}(n).

When k=n+1k=n+1

(n+1)!(a00!+a11!+...+an+1(n+1)!)=(n+1)(n)!(a00!+a11!+...+ann!)+an+1(n+1)! \left(\frac{{a}^{0}}{0!} + \frac{{a}^{1}}{1!} + ...+ \frac{{a}^{n+1}}{(n+1)!}\right) = (n+1)(n)! \left(\frac{{a}^{0}}{0!} + \frac{{a}^{1}}{1!} + ...+ \frac{{a}^{n}}{n!}\right) + {a}^{n+1}

(n+1)!(k=0n+1akk!)=(n+1)Pa(n)+an+1=Pa(n+1)(n+1)!\left( \sum _{ k=0 }^{ n+1 }{ \frac { { a }^{ k } }{ k! } } \right) = (n+1)\cdot {P}_{a}(n) + {a}^{n+1} = {P}_{a}(n+1)

Notice that the sum k=0nakk! \sum _{ k=0 }^{ n }{ \frac { { a }^{ k } }{ k! } } approaches ea{e}^{a} for large nn.

Hence, Pa(n)ean!{ P }_{ a }\left( n \right) \sim { e }^{ a }n! for large nn.

Note: the way I found this recurrence relation is by investigating the integral Pa(n)=aeaxxndx.{ P }_{ a }(n)=\int _{ a }^{ \infty }{ { e }^{ a-x } } { x }^{ n }dx . As an exercise, prove that this integral is equivalent to the defined recurrence equation.

Check out my other notes at Proof, Disproof, and Derivation

Note by Steven Zheng
5 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...