Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Making sense of a sequence

  1. Apr 21, 2010 #1
    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 [Broken]

    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!
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Apr 21, 2010 #2
    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

    [tex] A=\sum_{i=1}^n {{T}\over{c(i)}} [/tex]

    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.

    [tex] A=\sum_{i=1}^n \prod_{k \ne i} c(k)[/tex]

    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.
    Last edited by a moderator: May 4, 2017
  4. Apr 22, 2010 #3
    Nice one! None of the coefficients should be zero, so I won't have to worry about that. Thanks a lot mate.
  5. Apr 22, 2010 #4


    User Avatar
    Science Advisor

    Hi, you can also find an explicit formula. If f is your function, T your product to begin with, and [tex]x_i[/tex] the components, you will have [tex]f^k(x_i)=T^{\frac{(n-1)^k-(-1)^k}{n}}x_i^{(-1)^k}[/tex] 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, [tex]f(x_i) = 0[/tex] for all i, and if you exactly one zero, say [tex]x_j[/tex], then [tex]f(x_i)=0[/tex] for all [tex]i \not = j[/tex], and [tex]f(f(x_i)) = 0[/tex] for all i, which is not a particulary interesting case.
    Last edited: Apr 22, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook