Thank you so much. I can't believe how much money I'm paying my university, and all they do to teach us is "Theorem x: , Proof:" over and over again with no actual explanation as to what is going on. All the while this content is free on youtube
Amazing video so helpful :) just wanted to let you know that there was a slight mistake around 17:00 it should have been alpha sub k times n to the k-1 three to the n and similar for beta so beta sub m times n to the n-1. Great video again :)
Can't respond directly, so I hope you see this Iban Ariza, If the last digit is 0 or 1, then you can do anything. (so 2g(n-1)) If the last digit is 2, then you can't have 10 preceding it, but you can have anything else, like 00,01,11,20,02,12,21,22.
Hi Trev, thanks for the informative and clear video, I was just wondering though what is the alpha and beta technique called so I can look up more theory stuff on it. Thank you.
Lets say that we are looking for the number g(n) of ternary strings of length n that do not contain 102 as a substring. How would you approach this problem? If the last digit is {0,1,2} then, you can have any value for g(n-1) (either 0,1,2), so 3g(n-1). Also, if the second to last digit contains a {1,2}, then you can have any value for g(n-2) {0,1,2} so it would be g(n-2) 3 times. However, if you have the last two digits be 02, then you cannot have 1 on the prior term to those two and so it would result in 2g(n-3). So the recurrence relation would be 3g(n-1)+3g(n-2)+2g(n-3)? I know it is probably wrong. How would you solve it?
Hey Trev, I might have missed something, but in your explanation of having the same roots and all, shouldn't the last term be alpha * n ^ (k-1)? Apologies if i'm unclear, I'm not sure how to type out an expression. But yeah, am I supposed to count the number of roots starting from 0 or 1?
at 1:17, the equation should be a(n) - a(n-1) = kn and the solution should be a(n) = c + E(k*i) instead of E(k) Please Rectify. Do tell me if I'm wrong though, or if I have misunderstood anything.
A derivation of the form of the solution given roots of the characteristic polynomial would be nice. Does this require z-transforms and Cauchy's residue theorem? Or is there an easier way? I suppose there is always guess and check.
If the (n-1)th is 0,Can first n-2 positions be anything they want? . There can be consecutive 1s in first n-2 positions. Isnt it?(regarding “= an-1 + an-2”)
hello. I think there is a problem in the bit example. The a1 should be 2 as there can be a 1 or 0. a2 can be (00 01 10) so there can be 3 a2. This means that first is 2 and the second is 3 than you can find the rest of the examples from there. for example a3 is 5 and a4 is 8 and a5 is 13. Hope this helps everyone that is training for their exams and thanks for the video!
I'm a little unclear when you say that for anything else a(n-1), you can order it however you want. Say the last number in the binary string is 0. You say that for a(n-1), we can order it however we want. But that's not exactly true, because if we order, say, a length 5 binary string as 10110, that's clearly not allowed because there's two consecutive 1s. Could someone clarify this for me?
Way late to the party, but for anyone else with this question: a value denoted by a(n) always refers to the amount of "right" ways that the n elements can be organized. That is to say, the number of ways that a string of n binary elements with no consecutive ones can be created equals a(n). So a(n-1) is simply the amount of "correct" strings of n-1 binary elements.
can someone explain why if the string ends with 0 theres an-1 ways of making the strings? i get why it's an-1 but doesn't it have to count for the strings that dont have consecutive 1s?
For the second example, a[n]-4a[n-1]+4a[n-2]=0, a[0]=1 a[1]=3. Using this equation, a[2]-4(3)+4(1)=0, so a[2]-8=0, or a[2]=8. Using the equation a[n] = 2^n (1+(1/2)n), a[2] = 2^(2) (1+(1/2)2) = 4(2) = 8. So both are the same answer. Be careful with the homogeneous systems as you may flip your signs when looking at the original equation.
In the final problem, I am finding the answer that you have posted *(-1). I do this a lot as a mistake, but I can't find the specific error in this case. Maybe someone can confirm error? In any case, thank you very much for these lessons.
sir can We take the chareterstic polynomial in reverse In Ur example You have Shown r square minus r minus 6 so Can we tak in reverse Like -6square minus 1 plus 1 ?? Iz It correct ?
"Terms sum to zero." Same as homogeneous differential equations. There is no forcing function involved. The response (sequence) depends only on the recurrence relation (characteristic equation) and the initial conditions.
4:12 to 4:32 really just took off. No idea what's happening there. We didn't follow any of the processes that were just established. Edit: Okay, I see. We just did the entire thing completely backward. Now, I need a Trev video for how to factor.
probably to make it more clear that the sign changes with the power. It can be easier to recognize if it is written like (-2)^n instead of (-2^n), especially if your attention is focused on the harder parts of the problem.
![[Discrete Mathematics] Homogeneous Recurrence Relations Examples](http://i.ytimg.com/vi/Otj2ypYXn0Q/mqdefault.jpg)
![[Discrete Mathematics] Homogeneous Recurrence Relations Examples](/img/tr.png)
dude at 16:31,there's an error-the last term should have the power "k-1",and not "k"
I was going to comment the same thing. I think he knows the answer and just made a small error there.
I thoght the same
Yup noticed it too.....
Exactly! You are right
4 years later and yeah that's an error.
"this is more of a mechanics guide, rather than a theoretical guide" THANK YOU! All I can find about this is theory's about fibonacci lol
What a lifesaver it was to find this video < 2 days before my final, phew
I studied this just one night before exams and understood very well. Thanks for the tutorial bro
Awesome tutor. You are saving lives around the world and making demystifying rather seemingly complex concepts. Thank you very much
Best damn tutor I have been watching so far, really helped me get ready for my discrete final.
Thank you so much. I can't believe how much money I'm paying my university, and all they do to teach us is "Theorem x: , Proof:" over and over again with no actual explanation as to what is going on. All the while this content is free on youtube
This worked, the first 9 minutes had the explanations I was looking for.
Amazing video so helpful :) just wanted to let you know that there was a slight mistake around 17:00 it should have been alpha sub k times n to the k-1 three to the n and similar for beta so beta sub m times n to the n-1. Great video again :)
Joshua Uwaifo*times n to the m-1
+Joshua Uwaifo Was thinking the same thing too. Good observation.
I think you're right!
for same root:
An= alpha(k) * n^(k-1) * (3)^n
Tyson Tamang yep
Can't respond directly, so I hope you see this Iban Ariza,
If the last digit is 0 or 1, then you can do anything. (so 2g(n-1))
If the last digit is 2, then you can't have 10 preceding it, but you can have anything else, like 00,01,11,20,02,12,21,22.
Hi Trev, thanks for the informative and clear video, I was just wondering though what is the alpha and beta technique called so I can look up more theory stuff on it. Thank you.
Lets say that we are looking for the number g(n) of ternary strings of length n that do not contain 102 as a substring. How would you approach this problem?
If the last digit is {0,1,2} then, you can have any value for g(n-1) (either 0,1,2), so 3g(n-1). Also, if the second to last digit contains a {1,2}, then you can have any value for g(n-2) {0,1,2} so it would be g(n-2) 3 times. However, if you have the last two digits be 02, then you cannot have 1 on the prior term to those two and so it would result in 2g(n-3). So the recurrence relation would be 3g(n-1)+3g(n-2)+2g(n-3)? I know it is probably wrong. How would you solve it?
yes, same for m at 17:22 the last beta term should have "n" to the power of "m-1"
"ok, we have some room here, let's use this room" instead of "ok we will use the next page" hahaha typical Maths person :DD
16:43, isn't the kth term on the right supposed to have n raised to the power of k-1 instead of k?
Yes. It's would be k - 1
Holy shit! Thank you!
What you explained in 3 minutes (the characteristic polynomial) took my professor 25 mins to explain!
Correct dude😅
20:13 a0=1, a1=2 I used these parameters to calculate Fibonacci number which took me a while to figure why I was wrong.
This is very helpful. But what happens if the roots are complex(imaginary)? Do we introduce sin/cos in the solution?
Hey Trev, I might have missed something, but in your explanation of having the same roots and all, shouldn't the last term be alpha * n ^ (k-1)?
Apologies if i'm unclear, I'm not sure how to type out an expression.
But yeah, am I supposed to count the number of roots starting from 0 or 1?
You are correct
Hi Trev,
Can you go over the algebra for when r= (1+- sq(5))/2
Free and easy-to-understand lessons, this is the guy who contributes to evolution by passing down knowledge to generations without any financial cost
Wow good biological perspective, I never thought about it that way
What will the form of An if we get imaginary roots?
Thanks a lot, Sir, your explanations were clear and I understood the work! @Stellenbosch University & UNISA.
Great! I'm watching this after 8 years.
You're not alone
Damn bro......! You are definitely a life saver.... before my exams....thank you bro....!
Thank you so so much, my exam is tomorrow and if I do well it's all thanks to you, I wish you the best!
at 1:17, the equation should be a(n) - a(n-1) = kn
and the solution should be a(n) = c + E(k*i) instead of E(k)
Please Rectify.
Do tell me if I'm wrong though, or if I have misunderstood anything.
A derivation of the form of the solution given roots of the characteristic polynomial would be nice.
Does this require z-transforms and Cauchy's residue theorem? Or is there an easier way? I suppose there is always guess and check.
If the (n-1)th is 0,Can first n-2 positions be anything they want? . There can be consecutive 1s in first n-2 positions. Isnt it?(regarding “= an-1 + an-2”)
This was a freaking brilliant video. You explained in a vastly superior way than the way my notes did
hello. I think there is a problem in the bit example. The a1 should be 2 as there can be a 1 or 0. a2 can be (00 01 10) so there can be 3 a2. This means that first is 2 and the second is 3 than you can find the rest of the examples from there. for example a3 is 5 and a4 is 8 and a5 is 13. Hope this helps everyone that is training for their exams and thanks for the video!
thank you from the bottom of my heart
You are totally AWESOME thank you so much for this series teachers like you are unique I hope you will post more videos in future thank you so much
wow it really really magic you saved my grade ,and time
Thanks allot man, you're really good at explaining stuff
I want to ask why is if the r = 3 only. Then we must write C1 (3^n) + C2 n(3^n). Why is there an n in the second C
thank you so much for making this tutorial :)
Why do you multiply the first equation twice at 7:25?
I know this is 9 months late, but for anyone else wondering the same thing. It's to cancel out the Beta to get A on its own.
I'm a little unclear when you say that for anything else a(n-1), you can order it however you want. Say the last number in the binary string is 0. You say that for a(n-1), we can order it however we want. But that's not exactly true, because if we order, say, a length 5 binary string as 10110, that's clearly not allowed because there's two consecutive 1s. Could someone clarify this for me?
Basically he means that you can place any number(n-1) at that particular place,not the whole number.
Way late to the party, but for anyone else with this question: a value denoted by a(n) always refers to the amount of "right" ways that the n elements can be organized. That is to say, the number of ways that a string of n binary elements with no consecutive ones can be created equals a(n). So a(n-1) is simply the amount of "correct" strings of n-1 binary elements.
Thank you for the videos. May I ask what app/software you use?
Clear and too the point explanation, Great Job :-)
what would be the characteristic eqn of : An = 2An-1 - 2An-2 ??
its x^2 - 2x + 2 = 0 right?
but soln in my book and on site it says x^2 - 2x - 2 = 0
I was hoping for when we have 3 roots how can we solve for the Constant coffeciants :/ still this made it more clear so thank you.
simply evaluate a0, a1, a2, now 3 equation and 3 unknown, the solve
is a0 taken as 0 instead of 1? because alpha=1/√5 and beta=-1/√5 is only attainable in that condition...Am I missing something?
can someone explain why if the string ends with 0 theres an-1 ways of making the strings? i get why it's an-1 but doesn't it have to count for the strings that dont have consecutive 1s?
Is it possible for alfa and beta to be the same value?
Thankyou thus helped a lot
Learn a lot from this tutorial
At 17:19 the alpha and beta should start at alpha0 and beta 0 not alpha1 and beta 1.. right??? someone answer ...
Find the solution to the recurrence relation an =6an-1 +11an-2 -6an-3 with a0=2, a1=5 and a2=15.
Don't you think a0 should be 0 here at 20:10 because the string length is 0 hence we can't have anything of length of 0. Appreciate you response!
Yeh Im confused with that aswell, it's been 10 months, do you know the answer now? :)
@@PedroMiguel-iw5ul It’s been 5 years, have you figured it out yet?
Thank you very much. Your videos are very helpful.
there is a mistake at 16:41, shouldn't it be (alpha)k*nˆ(k-1) instead of (alpha)k*nˆk
where can i find the proof for the formula ( a_n = alpha(3^n) +beta(-2^n) ???? plz help[
Thank you so much.. your explanations better than my teacher lol
i can not thank u enough ur a hero
love ur handwriting
Does the order of roots matter when we apply them to the formulas? I am a little bit confused, any explanation appreciated!
It's not a problem because at that time the alpha and beta values changes. And finally balance that formula
Thanks pal! This is just awesome.
16:15 - Why is it not n to the (k-1)?
can someone tell me (7:00) why he put 1 instead of 8 when a1 is basically 8 ?
Why is it that for the second example, A(2) isn't the same answer for the recurrence relation equation and for the homogeneous equation?
For the second example, a[n]-4a[n-1]+4a[n-2]=0, a[0]=1 a[1]=3. Using this equation, a[2]-4(3)+4(1)=0, so a[2]-8=0, or a[2]=8. Using the equation a[n] = 2^n (1+(1/2)n), a[2] = 2^(2) (1+(1/2)2) = 4(2) = 8. So both are the same answer. Be careful with the homogeneous systems as you may flip your signs when looking at the original equation.
Thanks a lot 😄
love u man thank u so much for giving us free knowledge
for the Fibonacci series solution..... do we take a0 = 1 and a1 =1 or do we take a0 = 1 and a1=2?
Fibonacci technically starts at a_0=1 and a_1=1. The Lucas sequence starts at a_0=1 and a_1=2, even though they're both basically the same.
Can you please eli5 the bit string problem?
very much helpful
In the final problem, I am finding the answer that you have posted *(-1). I do this a lot as a mistake, but I can't find the specific error in this case. Maybe someone can confirm error?
In any case, thank you very much for these lessons.
The mistake is in the premise that a0 = 0.
In Fibonacci a0 = a1 = 1.
The answer written there is only attainable with the correct initial conditions.
what does that mean by the part "how many ways can we have zero?" at 20:04 ??
help me
Thank you..
dude you are best
sir can We take the chareterstic polynomial in reverse In Ur example You have Shown r square minus r minus 6 so Can we tak in reverse Like -6square minus 1 plus 1 ?? Iz It correct ?
plss Do Reply
I'm not quite sure what you're asking, but I've never seen it done that way and I don't think it would work.
Thank you so much!
thanks so much...literally saved my existence.
what happens if d
thank you so much from turkey
21:00 classic dp problem... nice...!
Great video sir.. Thank You.
great video, was very helpful
you are the BEST !
Great tutorial but what if the an is squared already?
so helpful thank you
sir can you explain that how to solve the expression
How do you solve T(n)=Theta(n)+4T(n/16)+4T(n/6)+8T(n/16)
Why at 13:40 it is 2 to the n plus n 2 to the n-1? where the n-1 came from?
He's just using exponent properties here.
1/2 is the same thing as saying 2^-1
2^-1 * 2^n = 2^(n-1)
Amazing, thank u
Thanks! This vid really helped! :)
Thankyou very much Sir
I'm still very confused by this.
Why are we changing an to rn and why is it automatically equal to 0.
Which software are you using?
I was using Windows Journal when this video was recorded. I use PDF Annotator now. (+ OBS for screen recording)
how do you describe a homogeneous recurrence relation with words?
"Terms sum to zero." Same as homogeneous differential equations. There is no forcing function involved. The response (sequence) depends only on the recurrence relation (characteristic equation) and the initial conditions.
Hello sir ,this can not be solved using Generating Functions?
+samuel jawahar Yes, but it is not introduced in the series until a few videos later.
thanks a lot sir ,may i know the subject i should know to solve "stackoverflow.com/questions/11382189/number-of-ways-to-place-kings-on-chess-board"
From where I can get more such questions
4:12 to 4:32 really just took off. No idea what's happening there. We didn't follow any of the processes that were just established.
Edit: Okay, I see. We just did the entire thing completely backward.
Now, I need a Trev video for how to factor.
Awesome!
thank you very much :)
I fucking love you man! Because of you I am gonna pass my CA2!
Hey!! Did you?
Is there a reason that at step 3 that the bracket placement differs per term?
I'm not sure what you mean here.
I think he's talking about 5:26, where An = alpha(3^n) + beta(-2)^n
Yeah
probably to make it more clear that the sign changes with the power. It can be easier to recognize if it is written like (-2)^n instead of (-2^n), especially if your attention is focused on the harder parts of the problem.
this video is very useful to me because i have a exam on Monday i hope i write exam well
Legendary!
god bless u