sidef-scripts/Math/double_summation_formula.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 14 November 2019
# https://github.com/trizen

# Single summation formula for a double summation.

# Given any function f(k), let:
#   F(n) = Sum_{k=1..n} f(k)
#   S(n) = Sum_{k=1..n} F(k)

# then:
#   S(n) = Sum_{k=1..n} Sum_{j=1..k} f(j)
#   S(n) = Sum_{k=1..n} f(k) * (n - k + 1)

# By splitting the sum into two sums, we get:
#   A(n) = Sum_{k=1..n} f(k)
#   B(n) = Sum_{k=1..n} f(k)*k

# Which allows us to represent S(n) as:
#   S(n) = (n+1)*A(n) - B(n)

func f(k) {     # any function f(k)
    k.euler_phi
}

func F(n) {     # partial sums of f(k)
    sum(1..n, {|k|
        f(k)
    })
}

func S1(n) {     # partial sums of F(k)
    sum(1..n, {|k|
        F(k)
    })
}

func S2(n) {     # equivalent with S1(n)
    sum(1..n, {|k|
        f(k) * (n - k + 1)
    })
}

#-------------------------------

func A(n) {
    sum(1..n, {|k|
        f(k)
    })
}

func B(n) {
    sum(1..n, {|k|
        k * f(k)
    })
}

func S3(n) {
    (n+1)*A(n) - B(n)
}

#-------------------------------

say F(100)       #=> 3044
say S1(100)      #=> 104359
say S2(100)      #=> 104359
say S3(100)      #=> 104359