If f(0) =1, f(x) =x+f(x-1) for x>0 calculate f(100)?

Question

If f(0) =1, f(x) =x+f(x-1) for x>0 calculate f(100)?

Answer 1

If f(0) =1, f(x) =x+f(x-1) for x>0 calculate f(100)?

 

f(0)=1

f(1)=1 + f(0) = 1 + 1 = 2

f(2)=2 + f(1) = 2 + 2 = 4

f(3)=3 + f(2) = 3 + 4 = 7

f(4)=4 + f(3) = 4 + 7 = 11

f(5)=5 + f(4) = 5 + 11 = 16

...

f(100) = 100 + f(99) = 100 + 4951 = 5051

 

Wait !! How did I know that f(99) was 4951 ??    Good question !

 

Each f(x) for x>1 is x plus [the sum of the numbers from 1 to (x-1)] + 1

          Remember, f(0)=1

 

So, for example, the f(4)=11 because it is 4 + [sum of the numbers from 1 to 3] + 1

                                    =                       4 +             6                                   +  1

                                    =                                       11

 

Note: Gauss' formula for the sum of the numbers from 1 to N, which is N(N+1)/2, appears at all levels of math and computer science and ...    PLZ memorize it.

 

(p.s.,  Even the best minds might not notice that f(0)=1, so if you didn't notice it, you're typical).

Answer 2

The rule for the function says take x and add it to the previous value of the function.  So if you just look at the integers, you have a sequence where the difference between each value and the one before is increasing by 1 at a time.  That's not the same as an arithmetic sequence, because in an arithmetic sequence, the difference between each value is a constant.

 

So the difference between terms f(0) and f(1) is 1, the difference between f(1) and f(2) is 2, the difference between f(2) and f(3) is 3, etc. 

 

What about the difference between the differences themselves -- you could call those the "second differences."  Since the first differences are 1, 2, 3, 4, etc., the second differences are 1, 1, 1, 1, etc.  It turns out that when the second differences are constant, the sequence is defined by a quadratic formula.  That is, f(x) = ax² + bx + c.  We just need to find our what a, b, and c are.

 

Let's see what the behavior of the function is for the first few integers.

 

f(0) = a*0² + b*0 + c = c.  We know that f(0) = 1, so c = 1

 

Now we know that the formula is f(x) = ax² + bx + 1.

 

Let's try f(1).

 

f(1) = 1 + f(1-1) = 1 + f(0) = 1 + 1 = 2

 

But f(1) is a*1² + b*1 + 1 = a + b + 1.  So a + b + 1 = 2, so a + b = 1.

 

Let's try f(2).

 

f(2) = 2 + f(2-1) = 2 + f(1) = 2 + 2 = 4

 

But f(2) is a*2² + b*2 + 1 = 4a + 2b + 1 = 4.  So 4a + 2b = 3

 

Now we have two equations, which we can solve together:

 

 

a + b = 1

4a + 2b = 3

 

2a + 2b = 2

4a + 2b = 3

 

Subtract the first equation from the second, and you get 2a = 1, so a = 1/2.  And since a + b = 1, b = 1/2 as well.

 

So the function is f(x) = 1/2 x² + 1/2 x + 1 = (x² + x + 2) / 2

 

Let's see what f(100) is:

 

f(100) = (100² + 100 + 2) / 2 = (10000 + 100 + 2) / 2 = 10102 / 2 = 5051

 

 

Answer 3

f(100) = 100 + f(99)

f(100) = 100 + 99 + f(98)

f(100) = 100 + 99 + 98 + f(97)

 

and so on

 

This is an arithmetic series.

 

S₁₀₀  = (100/2)(1 + 100)

S₁₀₀ = 5050