# Let F be a function defined for all nonnegative integers by the following recursive definition

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

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

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

Then

$$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

$$c_+2^n+c_-(-1)^n.$$

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

Hence

$$F(n)=\frac{2^n-(-1)^n}3.$$

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

$$F(0)=0,\\F(1)=1,\\F(3)=2F(1)+F(2)=F(2)+2\\F(4)=2F(2)+F(3)=3F(2)+2,\\F(5)=2F(3)+F(4)=5F(2)+6.$$

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