Recurrence Relations (need help)

Solve the following for ana_n given that a0=0a_0=0 and a1=1a_1=1

  1. an=an1+2an2+na_n=a_{n-1}+2a_{n-2}+n

  2. an=an1+2an2+n2a_n=a_{n-1}+2a_{n-2}+n^2

  3. an=2an1an2+n2a_n=2a_{n-1}-a_{n-2}+n^2

  4. an=an1+2an2+2na_n=a_{n-1}+2a_{n-2}+2^n

  5. an=an1an2a_n=a_{n-1}a_{n-2} (with initial conditions a0=1a_0=1 and a1=2a_1=2)

  6. an2=an1an2a_n^2=a_{n-1}a_{n-2} (with initial conditions a0=1a_0=1 and a1=2a_1=2)

  7. an=nan1+an2a_n=na_{n-1}+a_{n-2}

  8. an=an12+an2a_n=a_{n-1}^2+a_{n-2}

  9. an=an12+an22a_n=a_{n-1}^2+a_{n-2}^2

Note by Aditya Raut
5 years, 9 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

For numbers 1-3, the trick is to use the characteristic equation to solve. First, eliminate all terms that are not in the form of iajia_j:

an=an1+2an2+nan1=an2+2an3+(n1)\begin{aligned}a_n&=a_{n-1}+2a_{n-2}+n\\a_{n-1}=a_{n-2}+2a_{n-3}+(n-1)\end{aligned}

Subtracting the two, we get

anan1=an1+an22an3+1a_n-a_{n-1}=a_{n-1}+a_{n-2}-2a_{n-3}+1

But there's still a 11 in there! Do it again!

anan1=an1+an22an3+1an1an2=an2+an32an4+1\begin{aligned}a_n-a_{n-1}=a_{n-1}+a_{n-2}-2a_{n-3}+1\\ a_{n-1}-a_{n-2}=a_{n-2}+a_{n-3}-2a_{n-4}+1\end{aligned}

Subtract:

an2an1+an2=an13an3+2an4an3an1+an2+3an32an4=0\begin{aligned}a_n-2a_{n-1}+a_{n-2}=a_{n-1}-3a_{n-3}+2a_{n-4}\\a_n-3a_{n-1}+a_{n-2}+3a_{n-3}-2a_{n-4}=0\end{aligned}

Finally, we have it in the form we want. Now, we'll use the characteristic equation, which is an equation that looks like this:

x43x3+x2+3x2=0x^4-3x^3+x^2+3x-2=0

Basically, it takes its coefficients from the recurrence relation. Solving, we get x=1,1,1,2x=-1,1,1,2. From generating functions, we can now say that

an=c1(1)n+(c2+c3n)1n+c42na_n=c_1\cdot(-1)^n+(c_2+c_3n)\cdot1^n+c_4\cdot2^n

What we did here was take the roots of the equation and use their exponentials to develop the relation. For repeated roots, we have to create an entire polynomial with an ascending degree: if the root x0x_0 is repeated kk times, it'll be (c0+c1n+c2n2++cknk1)x0n(c_0+c_1n+c_2n^2+\dots+c_kn^{k-1})x_0^n. Lastly, we solve for c1,c2,c3,c4c_1,c_2,c_3,c_4 using a system of equations. Note that since there are four constants, we need to know four terms of the sequence, so we must compute a2=3a_2=3 and a3=8a_3=8. Solve the system of equations

{0=c1(1)0+(c2+c30)10+c4201=c1(1)1+(c2+c31)11+c4203=c1(1)2+(c2+c32)12+c4228=c1(1)3+(c2+c33)13+c423\begin{cases}0=c_1\cdot(-1)^0+(c_2+c_3\cdot0)\cdot1^0+c_4\cdot2^0\\1=c_1\cdot(-1)^1+(c_2+c_3\cdot1)\cdot1^1+c_4\cdot2^0\\3=c_1\cdot(-1)^2+(c_2+c_3\cdot2)\cdot1^2+c_4\cdot2^2\\8=c_1\cdot(-1)^3+(c_2+c_3\cdot3)\cdot1^3+c_4\cdot2^3\end{cases}

Eventually, we get (c1,c2,c3,c4)=(112,54,12,43)(c_1,c_2,c_3,c_4)=\left(-\frac1{12},-\frac54,-\frac12,\frac43\right), so

an=112(1)n54n2+432na_n=-\frac1{12}\cdot(-1)^n-\frac54-\frac{n}2+\frac43\cdot2^n

That technique takes care of 1-3. It also takes care of 5 as you can let an=2bna_n=2^{b_n} with b0=0b_0=0 and b1=1b_1=1 such that bn=bn1+bn2b_n=b_{n-1}+b_{n-2}, the famous Fibonacci sequence. Similarly, 6 has an=2bna_n=2^{b_n}, b0=0b_0=0, b1=1b_1=1, and 2bn=bn1+bn22b_n=b_{n-1}+b_{n-2}.

Cody Johnson - 5 years, 8 months ago

Log in to reply

Cody !!!! Even question 4 can be solved by your technique !!!! Just a little manipulation

Given thing an=an1+2an2+2na_n=a_{n-1}+2a_{n-2}+2^n

Next recurrence an1=an2+2an3+2n1a_{n-1}=a_{n-2}+2a_{n-3}+2^{n-1}

JUST MULTIPLY THIS BY 2 ON BOTH SIDES

2an1=2an2+4an3+2n2a_{n-1}=2a_{n-2}+4a_{n-3}+2^n

Now subtract from given !!!!

You get an3an1+4an3=0a_n-3a_{n-1}+4a_{n-3}=0

comparable to x33x2+4=0x^3-3x^2+4=0

Has roots x=1,2,2x=-1,2,2

And then we get an=c1(1)n+(c2+nc3)2na_n=c_1(-1)^n+(c_2+nc_3)2^n

Solve to get c1=19c_1=\frac{1}{9} , c2=19c_2=\frac{-1}{9} . c3=23c_3=\frac{2}{3}

And then an=19(1)n2n9+23n2na_n=\dfrac{1}{9}(-1)^n-\dfrac{2^n}{9}+\dfrac{2}{3} n2^n

Aditya Raut - 5 years, 8 months ago

Log in to reply

Very good!

Cody Johnson - 5 years, 8 months ago

Log in to reply

Wow, nice thought @Aditya Raut :)

Happy Melodies - 5 years, 6 months ago

Log in to reply

Thank you very very much Cody !!! Now please try for last three questions ...I found no way to solve them :(

Aditya Raut - 5 years, 8 months ago

Log in to reply

There is a typo at line 7: should be ana_n instead of an2a_{n-2}.

Happy Melodies - 5 years, 8 months ago

Log in to reply

Wow, that's insane. :P

Finn Hulse - 5 years, 7 months ago

Log in to reply

Try with generating functions.

Alessio Di Lorenzo - 5 years, 8 months ago

Log in to reply

The questions 7 to 9 are extremely tricky ..... No method worked :(

Aditya Raut - 5 years, 8 months ago

Log in to reply

I don't think the method of characteristics equation will work here... Instead, multiply the RHS (ana_n) and LHS by xnx^n, then sum the terms with respect to nn. Then, look for power series and simplify the expression,

Happy Melodies - 5 years, 3 months ago

Log in to reply

@Happy Melodies what are the terms LBS and RHS?

Mardokay Mosazghi - 5 years, 3 months ago

Log in to reply

@Mardokay Mosazghi Right Hand Side (of equation) for RHS and Left Hand Side for LHS

Happy Melodies - 5 years, 3 months ago

Log in to reply

Hmm Qn 7 is hard... (Refer to this link)[http://www.math.upenn.edu/~wilf/gfology2.pdf]. I think can still multiply by xnx^n on both sides then take sum. Differentiate the n(an1)n(a_{n-1}) term (with summation) then solve differential eqn.... Haven't worked that out but I think it might work. If you have no idea what I am talking about, the link above is a good guide to Generating Functions, which is very useful in solving recurrence type problems.

Happy Melodies - 5 years, 3 months ago

Log in to reply

@Happy Melodies I have worked that out the differential equation and it turns out to be unsolvable. The differential equaiton turns out to be x2f(x)+(x2+x1)f(x)+x=0x^{ 2 }f^{ ' }\left( x \right)+({ x }^{ 2 }+x-1)f(x)+x=0 where f(x)=n=0anxn\\ f(x)=\sum _{ n=0 }^{ \infty }{ { a }_{ n }{ x }^{ n } }

Ronak Agarwal - 5 years, 3 months ago

Log in to reply

@Ronak Agarwal Hmm i am not familiar with differential equation ... (Just started learning calculus) anyone can help?

Happy Melodies - 5 years, 3 months ago

Log in to reply

@Happy Melodies If you want to learn, I learned from Khan Academy. But if you want help in explaining this to Ronak, I'm afraid I can't help.

Finn Hulse - 5 years, 3 months ago

Log in to reply

@Finn Hulse Alright I will maybe after my exams

Happy Melodies - 5 years, 3 months ago

Log in to reply

Solve ana_{n} in terms of function of n only with initial values a0=0,a1=1,an=an12+an22a_{0}=0, a_{1}=1, a_{n}=a_{n-1}^2 + a_{n-2}^2



Here we observe one inequality. As series is growing,

an=>an1a_{n} => a_{n-1} It implies

an12+an22<=2an12a_{n-1}^2+ a_{n-2}^2 <= 2a_{n-1}^2

i.e.2an+12<=an<=2an12 2a_{n+1}^2<=a_{n} <= 2a_{n-1}^2

Observe an=2an12a_{n}=2a_{n-1}^2 is a series whose solution is

a_{n}=2^2^n

Hence we conclude that our solution will be of the same type

a_{n}=f^2^n

where f is a real number less than 2 (and definitely greater than zero.) Now all our efforts are to find f which satisfies above equation. As I worked out for calculating f,I came to know that it is irrational number and its value depends upon value of

a0,a1,a2,a3...a_{0},a_{1},a_{2},a_{3}...

For exact expression for f see this ,

" www.fq.math.ca/Scanned/11-4/aho-a.pdf "

Value of f up to fourteen significant digit is 1.11148222558297....

Another thing to point here is that ana_{n}=nearest integer to f^2^n

as value may be floating we have to take into account only integer values.

This is analytic solution but is correct for first 8th term.....For other terms more accurate value of f is needed otherwise it is perfect solution. Below is the verification of my solution...As i had said more significant digits are required for correctness.

n n an a_{n} f^2^n

 0                                  0                                             1
 1                                  1                                             1.2353
 2                                  1                                             1.5261
 3                                  2                                             2.3292
 4                                  5                                             5.4255
 5                                29                                            29.4361
 6                              866                                            866.485
 7                        750797                                           750797.4995
 8          563696885165                                            563696885249

Aamir Faisal Ansari - 5 years, 8 months ago

Log in to reply

Haa...one thing.....Not applicable for n=0 case

Aamir Faisal Ansari - 5 years, 8 months ago

Log in to reply

See i guess that n cannot take values 0 & 1 but when you start with n=2 and go on till 3 or 4 then you will start getting values now the difference of 2 consecutive terms will start forming an A.P. or G.P. that can be solved by method of differences,see if this works!!!

NITISH SHARMA - 5 years, 8 months ago

Log in to reply

Anyone knows how to solve Q2? I'm stuck with the characteristic equation method as well as generating funcs method...

Happy Melodies - 5 years, 8 months ago

Log in to reply

Do as Cody did !!!

given thing is an=an1+2an2+n2a_n=a_{n-1}+2a_{n-2}+n^2

Do for an1=an2+2an3+(n1)2a_{n-1}=a_{n-2}+2a_{n-3}+(n-1)^2

Which is an1=an2+2an3+n22n+1a_{n-1}=a_{n-2}+2a_{n-3}+n^2-2n+1.....(i)

Subtract this from Given one......... you will get an=2an1+an22an3+2n1a_{n}=2a_{n-1}+a_{n-2}-2a_{n-3}+2n-1.........(ii)

Now write the next recurrence............. an1=2an2+an32an4+2(n1)1a_{n-1}=2a_{n-2}+a_{n-3}-2a_{n-4}+2(n-1)-1

an1=2an2+an32an4+2n3a_{n-1}=2a_{n-2}+a_{n-3}-2a_{n-4}+2n-3................(iii)

Subtract (iii) from (ii) to get

an=3an1an23an3+2an4+2a_{n}=3a_{n-1}-a_{n-2}-3a_{n-3}+2a_{n-4}+2

But we got "2" here ...... Eliminate it from again one more recurrence !!!!!!!! an1=3an2an33an4+2an5+2a_{n-1}=3a_{n-2}-a_{n-3}-3a_{n-4}+2a_{n-5}+2

Subtracting, you get an=3an14an22an3+5an42an5a_n=3a_{n-1}-4a_{n-2}-2a_{n-3}+5a_{n-4}-2a_{n-5}

And now we find characteristic equation

x54x4+4x3+2x25x+2=0x^5-4x^4+4x^3+2x^2-5x+2=0

Has it's roots x=1,1,1,1,2x=-1,1,1,1,2

Next things you can find in Cody's solution :)

Aditya Raut - 5 years, 8 months ago

Log in to reply

What's q2?

Alessio Di Lorenzo - 5 years, 8 months ago

Log in to reply

As in the above point 2? Solving for ana_n

Happy Melodies - 5 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...