Let F be a function defined for all nonnegative integers by the following recursive definition. F(0) = 0, F(1)= 1 F(n + 2) = 2F(n) + F(n +1), n>0 Compute the first six values of F; that is, write the values of F(n) for n = 0,1,2,3,4,5

  • 1
    $\begingroup$ Well, I'm sure you can do it yourself. $\endgroup$
    – Nathaniel
    Oct 31, 2022 at 1:49
  • $\begingroup$ In fact, the problem cannot be solved because we can't know $F(2)$. $\endgroup$
    – user16034
    Nov 1, 2022 at 13:57

3 Answers 3


Let $F(n)=a^n$ and assume that the recurrence also holds for $n=0$.


$$a^{n+2}=2a^n+a^{n+1}$$ so that

$$a^2-a-2=0$$ and $a=-1,2$.

By the theory of linear recurrences, the general solution is of the form


The initial conditions tell us that $c_++c_-=0$ and $3\,c_+=1$.



Now plug $n=0,1,2,3,4,5$.




The recursive definition of F(n) is F(0) = 0 F(n) = F(n - 1) + n for all n ≥ 1

A recursive function is a function that refers to itself in its definition. The recursive function is called when a certain condition is met. The base case is a recursive function that terminates without calling itself. It is used to avoid infinite recursion.Let F be the function such that F(n) is the sum of the first n non-negative integers. F(0) = 0 , F(1) = O + 1 = 1 F(2) = 0 + 1 + 2 = 3 F(3) = 0 + 1 + 2 + 3 = 6 So, the function is adding up the first n non-negative integers. Therefore, the recursive definition of F(n) is F(0) = 0 F(n) = F(n - 1) + n for all n ≥ 1

  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Apr 19 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.