If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Evaluating sequences in recursive form

Sal shows how to evaluate a sequence that is defined with a recursive formula. This definition gives the base case and then defines how to find the subsequent terms using the base case.

Want to join the conversation?

  • aqualine tree style avatar for user NJK-Home
    I am confused by the requirement that n must be a whole number. When he does the recursion and uses 7.2 as n (as in g(7.2)) - isn't that breaking the requirement? He is using a non-whole number as the value of n. Initially, n is indeed a whole number, but then when the recursion happens he now using a non-whole number for n which should invalidate the requirement.
    (12 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Federico
    What is the explicit formula for that sequence (14,2,14,2)?
    (12 votes)
    Default Khan Academy avatar avatar for user
    • piceratops ultimate style avatar for user Anahadh Multani
      There is no explicit formula. If you recall from the first lesson of Geometric Sequences, (and if you haven't watched it, that's fine :D) the change between terms right next to each other (adjacent terms) have a common ratio. In this case, it doesn't.

      Let me give you a demonstration: a(k) = {14, 2, 14, 2...}

      2/14 = 0.14285...
      14/2 = 7

      What I've demonstrated to you, is that there is no common ratio. The ratios between the numbers are different.

      For example, in this sequence: a(k) = {1, 3, 9, 27...}

      3/1 = 3
      9/3 = 3
      27/9 = 3

      There is a common ratio here. Any given "k" is the previous "k" times 3.

      An essential part of explicit formulas is the common ratio! Since there is no common ratio in the first sequence, you can't represent it with an explicit formula. However, since there IS a common ratio in the second one, you CAN refer to it with an explicit formula: a(k) = 1(3)^k-1 => 3^k-1 (You don't need the one, but it always helps when you are confused about something, or something needs to be explained better)

      The only reason that we can represent this with a recursive formula is because of the base cases, parameters that describe particular properties of a function.

      This is an awesome question though! (And my apologies for being 2 years late)
      (22 votes)
  • aqualine ultimate style avatar for user koepkeb
    This is reminding me of linear formulas...is there any relation? I know (at least in this video) that the base isn't n=0...but the n=1 seems to be similar to the "y intercept" and the formula is the slope.
    (11 votes)
    Default Khan Academy avatar avatar for user
    • piceratops ultimate style avatar for user T H
      Good observation!
      If the difference between the consecutive terms is constant (like in the first example), then there is indeed a linear nature. We can see this, if we plot few points:
      (1, 4), (2, 7.2), (3, 10.4), (4, 13.6) etc.
      Note: We don't connect these points, because we are not trying to graph a line. We are trying to demonstrate a sequence.
      (13 votes)
  • blobby green style avatar for user Arbaaz Ibrahim
    With regards to the last example, how would we write it in an explicit way?
    (11 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user John Murphy
    I think I finally understand who these formulas work but I want to add that several times on this quiz and the last quiz, I was counted incorrect only because of parentheses. On some occasions the correct answer was something like (-3.5)^n-1 where I had put something like -3.5^(n-1). By merely removing parentheses. I usually had to put the exponents in parentheses because the -1 part would not stay as part of the exponent without them. On one occasion I had parentheses on the constant but not on the exponent like (3.3)^n . And I had to only remove the parentheses to get the correct answer. On all of these sequence problems I missed a few questions because of formatting only. I had lots of incorrect answers at first and most of them were legitimately wrong but when I finally started to figure it out I started to fail the quiz just because of formatting.
    (11 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user plpeaksterman67
    i am lost- i keep wanting to input numbers into the function and work from there, but the lesson is more on how to generate terms with the formula ...like the last one with the -6 and -4, i am wanting to put in numbers in to the functions and work from their, but the method is to make up numbers related to the base cases,...its like for some reason reminding me of algebraic inverse rations where if a is inversely related proportinal to b, the a = 1/b and then you derive a formula....my statement now is reflective of how I am not getting this..i will. just gotta perservere any advice?
    (6 votes)
    Default Khan Academy avatar avatar for user
    • orange juice squid orange style avatar for user graciousartist
      I think you may be confused with explicit functions in which you can just plug in any term you want, calculate, and you'll get the value of that term.

      In this video Sal is working with recursive functions and you cannot just input any number into a recursive function and get a result. For a recursive function you have to work out the value of the term that came before which means you have to start from the very first term.

      For example, @ :36 Sal is going through this process. He starts with g(1) and the definition of the function when n=1 is 4, therefore g(1)=4. When using a recursive function this is the starting point to work out the value of any term. If we want to work out the value of term 4 we have to work out g(2) and g(3) before we can work out g(4).

      The example that you use in your comment is slightly different. In this example @ Sal shows we are given are 2 base cases. So if we want to work out the value of term 2, well we don't have to do anything because it's already been defined as -4, so g(2)=-4. But if we want to work out the value of term 3 that's when we have to do some work. So, g(3)=f(n-2)+f(n-1) which is saying adding the value of the last 2 terms to each other gives us the value of the 3rd term. The calculations are, where we are replacing n with 3 in formula, g(3)=f(3-2)+f(3-1) which gives us g(3)=-6+-4 which gives us g(3)=-10. Therefore, the value of the 3rd term is -10.

      Does that make sense?
      (11 votes)
  • leaf green style avatar for user emilyship
    When do you know when to use a recursive formula?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • leaf blue style avatar for user Pi is the best
    What is the benefit of using a recursive formula over an explicit formula? Could you please give an example? For the first example in the video, it looks like a lot of work to have to work backwards once you start getting to higher function input numbers with a recursive formula.
    (5 votes)
    Default Khan Academy avatar avatar for user
    • leaf orange style avatar for user YanSu
      Recursive: Less work when you bring in more conditions, like x must be a real integer, x must be even, etc. To add in these conditions using recursive, you simply add these going down the list. It beats writing out everything in the explicit formula.
      (1 vote)
  • blobby green style avatar for user Ibrahim Ahmed
    fancy seeing fibonnaci sequence here
    (5 votes)
    Default Khan Academy avatar avatar for user
  • starky ultimate style avatar for user Yarlagadda Sathwik
    How would you solve:
    f(1)=−3
    f(n)=2⋅f(n−1)+1

    f(2)=?
    (2 votes)
    Default Khan Academy avatar avatar for user

Video transcript

- [Voiceover] So we've got the function g here, and what I want you to do is pause the video and figure out what g of one is, figure out what g of two is, g of three, and g of four. Figure out what all four of these are. All right, now let's work through this together. So g of one, if n is equal to one, well, then we're gonna hit this case right over here, if n is equal to one, g is equal to four. So that was pretty straightforward. Now, g of two, if n is equal to two, well, two is greater than one and it's a whole number, and so we would use this case. And this is interesting, because it's defined in terms of the function, but it's not defined in terms of g of n, but g of n minus one. So if n is two, 'cause we're evaluating g of two here, this is going to be g of two minus one, or g of one, plus 3.2. Plus 3.2. Well, what's that going to be? Well, g of one, we know is equal to four. We just figured that out. So four plus 3.2, that is 7.2. All right, let's keep going. G of three, we're gonna fall into this case again, because three is greater than one and it's a whole number. So this is going to be g of three minus one, or g of two, plus 3.2. Plus 3.2. Well, we know what g of two is. It's 7.2. We just figured that out. It is 7.2. 7.2 plus 3.2 is going to be equal to 10.4. And then g of four, well, we fall here again. This is gonna be g of three plus 3.2. G of three plus 3.2. What is that going to be equal to? Well, g of three we just figured out is 10.4. 10.4 plus 3.2 is going to be 13.6. And so what you have here, this is actually quite interesting. You can think of this function g, and we see that it's defined over all positive integers. Because it's defined over positive integers, we could think of it as defining a sequence, and we see what the sequence here is. The first term is four, second term is 7.2, next term is 10.4, next term is 13.6, and it could keep going on and on and on. And what's happening? What's happening in this sequence? Well, we're starting with four. We're starting with four, and this case of the function gave us that. If n is equal to four, if n is equal to one, the function is going to be equal to four, and then for each term after that, you take the previous term and you add 3.2. So we add 3.2 for the second term, we add 3.2, so we just keep adding, we just keep adding 3.2, not .32, 3.2 to get to the next term. Now, we could've defined it that way, we could've said, "Hey, let's have a sequence where the first term is four "and then we keep adding 3.2 to get each next term." But this is another interesting way of defining it. And this way of defining it, where we defined it as an algebraic function, a function that's defined over all positive integers, where we have a base case. And a base case, really, in this case, gave us our first term, and then we have this other case that's defined in terms of the function. Then you have to recurse backwards to eventually get to a base case. We call this a recursive function. Recursive function. So with this example, we're seeing how a recursive function can be used to define an actual sequence. And we went in order here, but you could've gone the other way around. If I said, "Oh, well, what's g of, "what's g of six?" Well, you'd go into this case, you'd say, "OK, that's going to be g of five plus 3.2." It's gonna be the previous term plus 3.2 if we view it as a sequence. Well, then we're gonna have to figure out what the previous term is. G of five is going to be g of four, g of four plus 3.2, and you would keep going back and back and back, but we've already figured out what g of four is. It's 13.6, so this is 16.8, and then if g of five is 16.8, 16.8, you add 3.2 there, you would get 20. So you could start at g of six and keep backing up, all the way until you get to g of one, and then you figure out what that is. You recurse back to your base case, and then you're able to fill in all of the blanks. Let's do a few more examples of this. So we have this function here. So let's say that this defines a sequence. Let's think about what the first four terms of that sequence are, and once again, I encourage you to pause the video and figure that out. All right, let's work through it. So h of one is, well, they very clearly tell us that's going to be 14. If n is equal to one, h is 14. H of two, well, now we're falling into this case, 'cause two is greater than one and it's a whole number, so it's gonna be 28 over h of one, over h of one. Well, we know h of one is 14, so it's gonna be 28 over 14, which is equal to two. Now h of three. H of three, we're gonna fall into this case again. It's gonna be 28, 28 divided by h of two, if we're thinking of this as a sequence, divided by the previous term in the sequence. So 28 divided by h of two, we know that h of two is equal to, is equal to two. We just figured that out. So we go back to 14, something very interesting. I think you see where this is going. H of four is gonna be 28 divided by h of three, 28 divided by h of three, which is 28 divided by, this is h of three right over here, we just figured that out, divided by 14, which is back to two. If we were to think of this as a sequence, we'd say, "All right, let's see, the first term is 14, "then we get to two, "then we go to 14, "then we get to two." So one way to think about this sequence is that we just keep alternating between 14 and twos. All of the odd terms of the sequence are 14, all of the even terms of the sequence are two. That's one way to think about it. Or another way to think about it is, we're starting with 14, and each successive term is the previous term divided, is 28 divided by the previous term. So here, 28 divided by 14 is two. 28 divided by two is 14. 28 divided by 14 is two. And we keep going on and on and on, and that's what was actually going on right over there. Let's do one more of these. And this one is interesting, because we now have, we now have two base cases. So let's think about this. This is, and actually let's just say we wanted to figure out, we wanted to figure out what, what f of four is. F of four, well, we're gonna fall into this case. Four is greater than two and it's a whole number. It's gonna be f of four minus two, so it's gonna be f of two plus f of four minus one, plus f of three. So f of four is gonna be the sum of the preceding two numbers. All right, so let's figure out what f of three is going to be. F of three, we fall into this case again, it's gonna be f of three minus two is f of one, plus f of three minus one, plus f of two, the sum of the preceding two numbers. So let's figure out what f of two is going to be. Well, now we're not doing the sum of the preceding two numbers anymore. We fall into this base case. N is now equal to two. It's going to be equal to negative four. And we're gonna have to figure out what f of one is as well. And we see when n is equal to one, f is equal to negative six. We have two base cases right over here. Base cases, cases that aren't defined in terms of the function itself. And you need that, 'cause otherwise you'd just be recursing forever. You would never get to actual numbers. But now we can use these to fill in the values up here. So the sequence is negative six, then we go to negative four as the second term, and then the third term is the sum of the previous two. Negative six plus negative four is negative 10. Negative six plus negative four is negative 10. And then the fourth term is the sum of the previous two. We see it right over here. The second term, f of two, plus f of three. Negative four plus negative 10 is negative 14. And we could keep going on and on and on like that. So this right over here is negative 14. So the whole point of this video, you're a little bit familiar with recursive functions now, and also you can see how these can be used to define actual sequences.