Solving a Quick and Easy Recursive Sequence

If you need to post a picture of your solution or idea:
#ChallengingMathProblems #SequencesAndSeries
EXPLORE 😎:

PLAYLISTS 🎵 :

[angelmendez-rivera]

I have an answer that I think will satisfy the people in the comments. You can obtain the exact solution to the equation with initial conditions a(0) = 1 and a(1) = 5 without needing to "guess" that the solution is a linear combination of powers of x and y.

Firstly, notice that a(n + 2) = 5·a(n + 1) – 6·a(n) is equivalent to a(n + 2) – 5·a(n + 1) + 6·a(n) = 0. Secondly, I want to introduce some notation to facilitate my explanation. As some of you may know, in mathematics, there exists something called the shift operator. What is the shift operator? The shift operator S is a function that takes a sequence a as an input and outputs a sequence b = S[a], with b(n) := a(n + 1). As such, a(n + 1) = S[a(n)]. With this formalism, a(n + 2) – 5·a(n + 1) + 6·a(n) = 0 can be rewritten as (S^2)[a(n)] – 5·S[a(n)] + 6·a(n) = 0. Since we are using operators, one can also write I[a(n)] = a(n), where I is the identity operator. With this, we have (S^2)[a(n)] – (5·S)[a(n)] + (6·I)[a(n)] = 0. One final simplification before moving on to the next step in the theory is to realize that the above is equivalent to (S^2 – 5·S + 6·I)[a(n)] = 0, because arithmetic operations on operators are defined pointwise.

Now that I have rewritten the equation in a more useful notation, explaining the solution method will be significantly easier. The idea here is to take advantage of factorization. As we all know, x^2 – 5·x + 6 = (x – 2)·(x – 3). It may surprise you to learn that multiplication of operators works similarly, and so, because S·I = I·S, it follows that S^2 – 5·S + 6·I = (S – 2·I)·(S – 3·I) = (S – 3·I)·(S – 2·I). As such, (S^2 – 5·S + 6·I)[a(n)] = 0 is equivalent to (S – 3·I)·(S – 2·I)[a(n)] = 0. This is the key idea to solving this equation. This factorization allows us to perform a substitution that simplifies this. For a start, you can define b(n) := (S – 2·I)[a(n)], and so this results in needing to solve (S – 3·I)[b(n)] = 0. Why is this important? Because this simplifies the equation significantly: rather than solving a(n + 2) = 5·a(n + 1) – 6·a(n), we can focus first on solving (S – 3·I)[b(n)] = 0, which simplifies to b(n + 1) – 3·b(n) = 0, which is equivalent to b(n + 1) = 3·b(n), which is *much* easier to solve. In fact, this just uses a basic recursion: b(n + 1) = 3·b(n) implies b(n) = 3·b(n – 1), so b(n + 1) = 3^2·b(n – 1), and by continuing this line of thought, you arrive simply at b(n + 1) = 3^(n + 1)·b(0), or just b(n) = 3^n·b(0). Since b(n) = (S – 2·I)[a(n)] = a(n + 1) – 2·a(n), it follows that b(0) = a(1) – 2·a(0) = 5 – 2·1 = 5 – 2 = 3, so b(n) = 3^n·3 = 3^(n + 1). Therefore, 3^(n + 1) = a(n + 1) – 2·a(n), and this is ultimately the equation you need to solve! Notice how we simplified the recursion from being second-order to simply being first-order.

Again, why does it matter that we simplified the equation to being first-order? Because we can simply use recursion to solve it, which you cannot do with higher-order equations. Notice that 3^(n + 1) = a(n + 1) – 2·a(n) is equivalent to a(n) = 3^n + 2·a(n – 1), which implies a(n – 1) = 3^(n – 1) + 2·a(n – 2), so a(n) = 3^n + 2·3^(n – 1) + 2^2·a(n – 2) = 3^n + 2·3^(n – 1) + 2^2·3^(n – 2) + 2^3·a(n – 3) = 2^0·3^(n – 0) + 2^1·3^(n – 1) + ••• + 2^(k – 1)·3^(n – k + 1) + 2^k·a(n – k) = 2^0·3^(n – 0) + 2^1·3^(n – 1) + ••• + 2^(k – 1)·3^[n – (k – 1)] + 2^k·a(n – k) = 2^0·3^(n – 0) + ••• + 2^n·a(0) = 2^0·3^(n – 0) + ••• + 2^n·1 = 2^0·3^(n – 0) + ••• + 2^n·3^0 = 2^0·3^(n – 0) + ••• + 2^n·3^(n – n) = 3^n·[2^0·3^(–0) + ••• + 2^n·3^(–n)] = 3^n·[(2/3)^0 + ••• + (2/3)^n] = 3^n·[1 – (2/3)^(n + 1)]/[1 – (2/3)] = 3^n·[1 – (2/3)^(n + 1)]/(1/3) = 3·3^n·[1 – (2/3)^(n + 1)] = 3^(n + 1)·[1 – (2/3)^(n + 1)] = 3^(n + 1) – 2^(n + 1), which is the result in the video, just shifted forward by 1, since the video used a shifted version of my sequence.

In fact, with this same method, you can prove, in full generality, that a(n + 2) – (u + v)·a(n – 1) + u·v·a(n) = 0 is solved by a(n) = A·u^n + B·v^n if u and v are distinct, where A and B are functions of a(0) and a(1). This, ultimately, is what answers the question of why we can assume the the solution looks like a(n) = x^n, which is what the video assumed. By the way, this method also works when solving differential equations, and the only distinction is that, instead of working with the shift operator S, you work with the derivative operator D, and this also answers the question of why, when solving differential equations, you always make the substitution y(t) = A·exp(r·t). The method proves that for y''(t) – (u + v)·y'(t) + u·v·y(t) = 0, with u and v distinct, the general solution is y(t) = A·exp(u·t) + B·exp(s·t). Whoa! What an uncanny similarity! Well, actually, the similarity is there because the theory of difference equations and the theory of differential equations are actually special cases of the same grand theory, called the theory of time scales, where a derivative operator corresponds to each time scale. So it is no surprise that the same method works in both theories. In fact, earlier, I said that a(n) = A·u^n + B·v^n, which is really the same thing as a(n) = A·exp[log(u)·n] + B·exp[log(v)·n], and this is almost identical to the solution y(t) = A·exp(u·t) + B·exp(v·t), where the distinction lies in that the former has logarithms. This is not surprising, though, since, as it happens, D = log(S). So the two linear operators are related.

[SyberMath]

Hello everyone:
I noticed a lot of people are asking where on earth y=x^n comes from. I know I just wrote it without giving you a background because I was trying to keep the video short. First off, we noticed that it works so the method is not incorrect!
This is very similar to solving linear homogenous differential equations where we find the characteristic equation and substitute to find the unknown coefficients.
You can also use generating functions to see what's going on here but I will keep this basic.
Consider the function f:R --> R satisfying
f(n+m)=f(n)f(m) for all values of n and m which we know is satisfied by f(n)=a^n for real a. We could proceed as follows:
Let m=1
f(n+1)=f(n)f(1). f(1) is a constant so let's sub f(1)=c for real c
f(n+1)-cf(n)=0. Now replace f(n) with a_n and you''ll get
a_{n+1}-ca_n=0 and this is satisfied by a_n=c^n
If we go by the characteristic equation, we sub a_n=r^n
a_n+1=r^{n+1}
r^{n+1}-cr^n=0
r^n(r-c)=0
r=c
So a_n=c^n
You can apply this to any linear homogenous recursion as long as the roots of the characteristic equation are all distinct. If the roots are not distinct, then it's a different story 😁
By the way, searching for recursions, I found the following video by @GVSUmath:
This gives you a good foundation.
And then I got recommended @blackpenredpen's video. I did not know he made one. It's a great video from a great mathematician. Check it out! 🤩
Sorry for the lengthy comment! I have a hard time keeping things brief. 😂😂😂
If you want brief and to the point solutions on calculus and other cool stuff, make sure to check my fellow YouTuber @Math Elite's channel:
And as always...be safe and keep up the good work!!!
💖

[keshavgupta]

This video cleared almost all doubts that I had with sequence and series..😊
♥️♥️🥰😍

[kuokenwei]

How can you just define an as x^n for sure ?
Have any clues ? Or we should exclude other possibilities first?

[pratimakumari]

I will never even ever knew that type of equation exist let's see how to solve it lol<3

[folarinolaloye]

Nice method Sir. From my end you can also see this as a difference equation of second order with initial conditions and solve using Z-transforms in the discrete frequency domain.

[panPetrff]

Rearrange into 2 cases:
a(n+2) - 2a(n+1) = 3*(a(n+1) - 2a(n)) (1)
a(n+2) - 3a(n+1) = 2*(a(n+1) - 3a(n)) (2)
We have 2 geometric sequences:
(1)
b(n) = a(1+n) - 2a(n)
b(1) = 5-2*1=3
b(n+1) = 3*b(n) = a(1+n+1) - 2a(n+1)
==> b(n) = 3^n
(2)
c(n) = a(1+n) - 3a(n)
c(1) = 5-3*1=2
c(n+1) = 2*b(n) = a(1+n+1) - 3a(n+1)
==> c(n) = 2^n
Result after substracting:
a(1+n) - 2a(n) = 3^n
-[a(1+n) - 3a(n)] = -[2^n]
a(n) = 3^n - 2^n

[水平線-gb]

Because many comments are asking why appears x^n, I will try my best to explain.

With any <An+2> = a*<An+1> + b*<An>, we can rewrite the recursive sequence as <An+2> - p*<An+1> = q* (<An+1> - p*<An>), so <An+1> - p*<An> = q^(n-1) * (<A2> - p*<A1>)

In this case, we can solve that (p, q) = (2, 3) or (3, 2), and then we get 2 formula:

<An+1> - 2*<An> = 3^(n-1) * (<A2> - 2*<A1>) = 3^(n-1) * (5 - 2*1) = 3^n
<An+1> - 3*<An> = 2^(n-1) * (<A2> - 3*<A1>) = 2^(n-1) * (5 - 3*1) = 2^n

Subtract each other and we can get <An> = 3^n - 2^n

[vacuumcarexpo]

I was able to solve this in the same way!

[aashsyed]

hello syber! did you watch the Micheal Penn integral livestream? i saw you in the chat!

[p_square]

Thank you SyberMath for making me a mod :)

[echandler]

IIRC you can derive this using generating functions, aka power series, where f(x)=sum(a[n]x^n.

[jeffburdette]

Reminds me of equating coefficients in DE

[hsjkdsgd]

Why choose x^n at start, why not something else?

[broytingaravsol]

a linear combination technique that is also implicated in ordinary differential equations

[riade-yet]

Yes very interesting. but is this merhod possible for general recursive relation looking like polynome.

[arundhatimukherjee]

I am not at all a good finder of sequences, but still trying:
an+2 = 5an+1 - 6an
or an+2 - 2an+1 = 3(an+1 - 2an)
or an - 2an-1 = 3(an-1 - 2an-2)
or an - 2an-1 = 3^(n-2)(a2 - 2a1) (using the above recursive relation n-2 times)
or an - 2an-1 = 3^(n-2)(5-2.1)=3^(n-1)
or 2(an-1 - 2an-2) = 2.3^(n-2)
Adding, an - 2²an-2 = 3^(n-1)+2.3^(n-2)
Again, 2²(an-2 - 2an-3) = 2².3^(n-3)
Adding, an - 2³an-3 = 3^(n-1)+2.3^(n-2)+2².3^(n-3)
Continuing in this way
an - 2^(n-1)a1 =
or, an = a1=1)
or an = summation (r goes from 1 to n) 2^(r-1).3^(n-r) = (3^n/2) summation (r goes from 1 to n) (2/3)^(r) = (3^n/2){2(1-(2/3)^(n))} = 3^n - 2^n for all positive integers n.🙂

[Romik]

why do we choose a geometric sequence, instead of for example arithmetic?

[shivam]

How can you just assume it is x^n at least give a hint of your reasoning for such a choice

[mohammadazadi]

Hi Dear friends.
I am confused by jumping at a powerd n as first assumtion.
What is ressons of this aproching?( sory .English isn, t my first languag)