Need help for Recurrence!

Hello! Any hints for this? (Characteristic eqn doesn't seem to work for me here...)

an=(n1)an1+na_n = (n-1) a_{n-1} +n.

Thanks! :) Please help reshare this too!

Note by Happy Melodies
5 years, 5 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

Sort by:

Top Newest

You have to do plug and chug

This is called plug :

an=(n1)((n2)an2+n1)+na_n = (n-1)((n-2)a_{n-2}+n-1) + n

This is called chug

an=(n1)(n2)an2+(n1)2+na_n = (n-1)(n-2)a_{n-2}+(n-1)^{2}+n

Continue doing this until you arrive at a base case....You can see the general form after a few chugs. which you can prove by induction....

Eddie The Head - 5 years, 5 months ago

Log in to reply

I don't think there is an easy way to do this. Clearly there is no characteristic polynomial as the coefficients are variable. I plugged it into wolfram alpha after working on it to no avail and its general form is an=2eΓ(n,1)1a_n=2e\Gamma(n,1)-1 where a1=1a_1=1.

Γ(a,x)\Gamma(a,x) is the Incomplete Gamma Function which I have no clue of its definition.

Daniel Liu - 5 years, 5 months ago

Log in to reply

My original strategy was to substitute bn=an+1c1anb_n=a_{n+1}-c_1a_n for some constant cc such that everything cancels out neatly, but it got really messy and I ended up having c1=n+n242c_1=\dfrac{-n+\sqrt{n^2-4}}{2} (which is almost certainly wrong) then I stopped.

Daniel Liu - 5 years, 5 months ago

Log in to reply

Yes me too! I got that too, but it doesn't work the same way as typical characteristic eqn with variables...

Happy Melodies - 5 years, 5 months ago

Log in to reply

Divide through by (n1)! (n-1)! to get an(n1)!=an2(n2)!+n(n1)! \frac{a_n}{(n-1)!} = \frac{a_{n-2}}{(n-2)!} + \frac{n}{(n-1)!} . Then if we let bn=an(n1)! b_n = \frac{a_n}{(n-1)!} , we should have b1=a1 b_1 = a_1 and bn=bn1+n(n1)! b_n = b_{n-1} + \frac{n}{(n-1)!} , so bn=a1+k=2nk(k1)! b_n = a_1 + \sum_{k=2}^{n} \frac{k}{(k-1)!} . Then an=a1(n1)!+k=2nk(n1)!(k1)! a_n = a_1(n-1)! + \sum_{k=2}^n \frac{k(n-1)!}{(k-1)!} . Perhaps that sum has a nice simple closed form?

Patrick Corn - 5 years, 5 months ago

Log in to reply

Is there a nice way to express the summation in a closed form? Summations in general do not count as a closed form. i=1ni\displaystyle\sum_{i=1}^ni is not a closed form, but n(n+1)2\dfrac{n(n+1)}{2} is.

Daniel Liu - 5 years, 5 months ago

Log in to reply

No, I don't think so. Although (k2)(k1)! \sum \frac{(k-2)}{(k-1)!} is telescoping, this still leaves 2(k1)! \sum \frac2{(k-1)!} , twice the partial sum for e e .

Patrick Corn - 5 years, 5 months ago

Log in to reply

I would use generating functions.

Sean Roberson - 5 years, 5 months ago

Log in to reply

a1=1,a2=3,a3=9,a4=31

Sai Satti - 5 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...