4

I have the following function:

f(n) = f(n - 1) + (n - 1)
f(0) = 0
n >= 0

I have n declared on column A, and need the result of f(n) on column B.

I'm trying to find the Excel formula equivalent for this function.

Sample Result:

A | B
--+--
0 | 0

or:

A | B
--+--
1 | 0

or:

A | B
--+--
4 | 6

but never:

A | B
--+--
0 | 0
1 | 0
2 | 1
...

The biggest problem is, I can't simulate the value of f(n - 1). So referencing the previous row like the above example is invalid. I'm almost sure the answer is trivial, I just can't find it.

0

8 Answers 8

16

Does this help?

f(n) = sum of all positive integers less than n

It should, especially with the help of some arithmetic.

OK, given that people are now posting answers with user defined functions, here is the answer

f(n) = (n-1)n/2

Update: For those who cannot see that the formula does not use any information from any other rows (see Stan R.'s comment below), I jumbled up the order a little bit:

 0  =(A1-1)*A1/2    0
 9  =(A2-1)*A2/2    36
 2  =(A3-1)*A3/2    1
 4  =(A4-1)*A4/2    6
 6  =(A5-1)*A5/2    15
 5  =(A6-1)*A6/2    10
10  =(A7-1)*A7/2    45
 8  =(A8-1)*A8/2    28
 3  =(A9-1)*A9/2    3
 7  =(A10-1)*A10/2  21
 1  =(A11-1)*A11/2  0
...
10
  • presumably f is just a stand in for a more complex recusive function Aug 3, 2009 at 23:22
  • @Scott Weinstein The question is the question. If am going to get downvoted for answering the question as it was posted, so be it. Aug 3, 2009 at 23:26
  • assuming that column A is going to be sequential then your example works.
    – Stan R.
    Aug 3, 2009 at 23:29
  • Scott, the question doesn't imply that at all. If the question is intended to mean, "How can I perform a general recursive function in Excel?" than, well, that's what the question should say. The less snarky version of Sinan's (completely correct) answer is: f(n + 1) = (n^2 + n)/2
    – Ibby
    Aug 3, 2009 at 23:31
  • good points, perhaps less presumption on my part... Aug 3, 2009 at 23:48
8

Do you need to solve it recursively? That's certainly not the nicest way to solve it:

Sum the numbers 1 to 10

   1 + 2 + 3 + 4 + 5
+ 10 + 9 + 8 + 7 + 6
  --  --  --  --  --
  11 +11 +11 +11 +11 = 55

or, as it's summarised, (n+1)(n/2) -- with n=10, this is obviously 11 x 5

2
  • 1
    Doh! Forgot about Gauss...
    – Greg
    Aug 3, 2009 at 23:33
  • I should point out that I'm actually solving for (n+1) as it's phrased in the question, but the normal expression of this problem is summing to a number, inclusive
    – Gareth
    Aug 3, 2009 at 23:37
3

The function can be restated to eliminate the recursion.

Let's take a couple of examples here...

f(4)=1+2+3=6
f(5)=1+2+3+4=10
f(6)=1+2+3+4+5=15

There's a pattern here:

f(4)=1+2+3=6=4*1.5
f(5)=1+2+3+4=10=5*2
f(6)=1+2+3+4+5=15=6*2.5

which means we can generalize the function to f(n)=1+2+...+n=n*(n-1)/2 for n>1 and f(n)=0 otherwise.

The resulting Excel formula can then be written as =IF(A5>1;A5*(A5-1)/2);0), assuming A5 contains n.

Obviously, if your formula is more complex than the one you gave, it may become quite a bit harder, and it may be a lot quicker and easier to just write a user defined function like the one suggested by Scott and then use that.

3

Excel has something called Array Formulas, which allows a function to return a set of values. You can read more about them here. These will effectively let you write, with some creativity, analogs to recursive algorithms. Array formulas must be entered in using Shift-Ctrl-Enter.

To answer your question, have an array function return 1 through n-1, and wrap it in a sum. Here, Indirect creates a reference, and A1 holds n:

=SUM( ROW( INDIRECT("1:"&A1-1) ) )
1
  • Thank you, I used your formula here. I was tearing my hair out trying to find a way to make {4,3,2,1} change when the cell value changed. Sep 30, 2020 at 15:53
2

Not sure how to do it with pure formulas. One option is a UDF

Public Function f(n As Integer) As Integer
    If (n = 0) Then
        f = 0
        Exit Function
    End If

    If (n > 0) Then
        f = f(n - 1) + (n - 1)
    End If
End Function

and then the formula is just =f(A1)

1
  • beat me with the code :P
    – Stan R.
    Aug 3, 2009 at 23:31
0

if understand you correctly then you are trying to create a recursive function and circular references in Excel are not allowed. Your best bet is to create your own worksheet function.

Press Alt+F11 to go into VB then Insert>Module then follow Scott's answer.

0

Typically the way that this is done is to define your own functions. In the VBA editor, insert a new module into your workbook and paste in the following function:

Function f(n As Integer)
    If n <= 0 Then
        f = 0
    Else
        f = f(n - 1) + (n - 1)
    End If
End Function

Now you can call this directly:

=f(A2)
0
=IF(MOD(A1,2)=0,(A1-1)*ROUND(A1/2,0), (A1) * ((A1-1)/2))

I don't know, if that is what you are looking for.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .