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.

 

[CellCoree]

I would approach this problem by first looking for patterns in the sequence. The first few terms already show a clear pattern, with each term being the sum of the previous term and a new term that is a product of the current number of variables. This suggests that the next term can be generated by simply multiplying the current term by the number of variables and adding it to the previous term.

To confirm this pattern, I would test it with a few more terms and see if it holds true. If it does, then I would write a simple algorithm in MATLAB to generate the nth term based on this pattern. This algorithm could be easily incorporated into a larger script for further analysis.

Additionally, I would also explore if there are any existing mathematical concepts or operations that could be applied to this sequence. For example, the sequence may be related to binomial coefficients or other combinatorial concepts. By researching and understanding these concepts, I may be able to find a more efficient or elegant way to generate the nth term.

Overall, as a scientist, I would use a combination of pattern recognition, testing, and research to generate an algorithm for this sequence and continue to refine it for optimal efficiency and accuracy.