How do I algorithmically generate the nth term of this sequence?

[FrankDrebon]

Hi all,

I have a term in an equation that grows in an intuitive manner each time I increase the number of variables.

Basically, for an input vector of size n, this term is a sum of n terms, each of which is a product of n-1 components in the vector. Put simply, it is the sum of each unique way that the components of the vector can be multiplied together as a product of n-1 components.

I've probably explained that badly, so the first few terms can be found in the image below:

http://img52.imageshack.us/img52/1779/cvalues.jpg

It is fairly easy to compute the next term myself. However, I'd like to be able to find an algorithm for generating the nth term for inclusion in a MATLAB script.

Essentially the problem boils down to "how do I generate the nth term algorithmically?" I've run out of ideas, but can't help but think there would be some (relatively) simple matrix operation that could generate this. Maybe the pattern-hunters amongst you will notice something I haven't.

Any thoughts or suggestions welcome!

 

[elect_eng]

Hi all,

I have a term in an equation that grows in an intuitive manner each time I increase the number of variables.

Basically, for an input vector of size n, this term is a sum of n terms, each of which is a product of n-1 components in the vector. Put simply, it is the sum of each unique way that the components of the vector can be multiplied together as a product of n-1 components.

I've probably explained that badly, so the first few terms can be found in the image below:

http://img52.imageshack.us/img52/1779/cvalues.jpg

It is fairly easy to compute the next term myself. However, I'd like to be able to find an algorithm for generating the nth term for inclusion in a MATLAB script.

Essentially the problem boils down to "how do I generate the nth term algorithmically?" I've run out of ideas, but can't help but think there would be some (relatively) simple matrix operation that could generate this. Maybe the pattern-hunters amongst you will notice something I haven't.

Any thoughts or suggestions welcome!

There is a trivially simple way to approach this. Notice that any term in your equation is the product of all coefficients (c(i), for i=1 ... n) with the exception of one. So, you can generate the total product of all coefficients (call it T), and then just do a summation over the terms, i.e. T/c(i).

In equation form this looks as follows:

T= product of all coefficients c(i) for i=1 ... n

$$A=\sum_{i=1}^n {{T}\over{c(i)}}$$

So bascially you have two independent (i.e. not nested) loops. The first loop does the total product, and the second does the summation you are interested in. The only thing you have to worry about is cases where a coefficient is zero, but this is easily handled with some if statements.

If you expect no zero coefficients, then the above method is easy. If you expect cases with zeros, then you may prefer another approach as follows.

$$A=\sum_{i=1}^n \prod_{k \ne i} c(k)$$

This is also easy, but now your two loops are nested. The outer loop does a summation and the inner loop does a product calculation, but always excludes one of the coefficients.

 

[FrankDrebon]

Nice one! None of the coefficients should be zero, so I won't have to worry about that. Thanks a lot mate.

 

[disregardthat]

Hi, you can also find an explicit formula. If f is your function, T your product to begin with, and $$x_i$$ the components, you will have $$f^k(x_i)=T^{\frac{(n-1)^k-(-1)^k}{n}}x_i^{(-1)^k}$$ which can be proven inductively.

This will however only work when you originally have non-zero components. If you have more than one zero to begin with, $$f(x_i) = 0$$ for all i, and if you exactly one zero, say $$x_j$$, then $$f(x_i)=0$$ for all $$i \not = j$$, and $$f(f(x_i)) = 0$$ for all i, which is not a particulary interesting case.