[go: up one dir, main page]
Scribd
Upload
13 views41 pages

Sums

Uploaded by

shoyeb haque

The document discusses various summation notations and methods for evaluating sums. It introduces common summation notations like the delimited form, generalized sigma form, and multiple sums. It also presents techniques like perturbation methods for manipulating sums and finding closed-form expressions. Examples are given of applying these methods to find closed forms for sums like the sum of squares and sums involving geometric progressions.

Copyright:

© All Rights Reserved
Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt

Sums

Uploaded by

shoyeb haque
13 views41 pages
The document discusses various summation notations and methods for evaluating sums. It introduces common summation notations like the delimited form, generalized sigma form, and multiple sums. It also presents techniques like perturbation methods for manipulating sums and finding closed-form expressions. Examples are given of applying these methods to find closed forms for sums like the sum of squares and sums involving geometric progressions.

Original Title

4. Sums

Copyright

© © All Rights Reserved

Available Formats

PPTX, PDF, TXT or read online from Scribd

Did you find this document useful?

Is this content inappropriate?

The document discusses various summation notations and methods for evaluating sums. It introduces common summation notations like the delimited form, generalized sigma form, and multiple sums. It also presents techniques like perturbation methods for manipulating sums and finding closed-form expressions. Examples are given of applying these methods to find closed forms for sums like the sum of squares and sums involving geometric progressions.

Copyright:

© All Rights Reserved
Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt
13 views41 pages

Sums

Uploaded by

shoyeb haque
The document discusses various summation notations and methods for evaluating sums. It introduces common summation notations like the delimited form, generalized sigma form, and multiple sums. It also presents techniques like perturbation methods for manipulating sums and finding closed-form expressions. Examples are given of applying these methods to find closed forms for sums like the sum of squares and sums involving geometric progressions.

Copyright:

© All Rights Reserved
Download as PPTX, PDF, TXT or read online from Scribd
Download as pptx, pdf, or txt
You are on page 1/ 41

Chapter 2

Sums
Notation
1+2+3+...+(n-1)+n

1+2+...+n

1+...+n

a1+a2+...+an
Terms -> ai, aj

1+2+...+2n-1
20+21+...+2n-1
Delimited Form Generalized-Sigma Form

Sigma Notation Relation under Σ

Find both Delimited and Generalized-Sigma Form of 1+3+...+n


1
Sum of Reciprocals of Prime Number = ∑ 𝑝
𝑝 ≤𝑛
𝑝 𝑝𝑟𝑖𝑚𝑒
Gives Prime Number
𝜋(𝑛)
1
= ∑ 𝑝𝑘
𝑘=1

∑ 𝑎𝑘 Change k to k+1
∑ 𝑎𝑘+1
1 ≤𝑘 ≤ 𝑛 1≤𝑘+1≤𝑛

𝑛 𝑛− 1
∑ 𝑎𝑘 Change k to k+1
∑ 𝑎𝑘+1
𝑘=1 𝑘=0
∑ 𝑎𝑘 Sum of all terms ak such that k is an integer
and satisfy a given property P(k)
𝑃( 𝑘)

[P Prime] =

True/False

∑ [ 𝑃 𝑃𝑟𝑖𝑚𝑒 ][ P ≤ N ]/ P → Kenneth E Iversion


𝑃
True/False

∑ 𝑎𝑘[ 𝑃 (𝑘)]
𝑘
Sums & Recurrence
The sum, Sn = is equvelent to,

S0 = a 0

Sn = sn-1 + an , n>0
Rn = α + nβ + γ proof
Find the closed form of Rn =
Tower of Hanoi
Problem:
In quicksort algorithm, one of the most methods for sorting data, data’s need to
compare with other element. The average number of comparison steps made by quicksort
when it is applied to n-items in random order satisfies the following recurrence,
C0 = 0
Cn = n+1+ , for n>0

1. From the given recurrence in anTn=bnTn-1+Cn


2. Find the value of summation factor (sn)
3. Prove that Cn=2(n+1)
4. Find C1, C2, C3
Manipulation of
Sums
Law/Rule Normal Algebra Sums
Distributive Law ab+ac=a(b+c)
Associative Law a+(b+c)=(a+b)+c
Commutative Law a+b=b+a
Law/Rule Normal Algebra Sums
Distributive Law ab+ac=a(b+c)
Associative Law a+(b+c)=(a+b)+c
Commutative Law a+b=b+a

Any order
Perturbation Method

𝑚 𝑛 𝑛
𝑖¿ ∑ 𝑎 𝑘+ ∑ 𝑎 𝑘=𝑎𝑚+ ∑ 𝑎 𝑘
𝑘=1 𝑘=𝑚 𝑘=1

𝑖𝑖 ¿ ∑ 𝑎 𝑘= 𝑎 0 + ∑ 𝑎𝑘
0 ≤ 𝑘 ≤𝑛 1 ≤𝑘 ≤𝑛
4. ∑ 𝑎𝑘+ ∑ 𝑎 𝑘= ∑ 𝑎 𝑘+ ∑ 𝑎𝑘
𝑘∈𝐾 𝑘∈𝐾 ’ 𝑘∈ 𝐾 ∩𝐾 ’ 𝑘∈ 𝐾 ∪ 𝐾 ’
𝐼𝑓 𝑆𝑛= ∑ 𝑎𝑘𝑡ℎ𝑒𝑛 𝑓𝑖𝑛𝑑 𝑆𝑛+𝑎 𝑛+1
0 ≤𝑘≤𝑛+1
Find the sum of geometric pogression using Perturbation Method

𝑆 𝑛= ∑ 𝑎𝑥 𝑘
0 ≤ 𝑘 ≤𝑛
Multiple Sums
∑ 𝑎 𝑗 𝑎𝑘
1≤ 𝑗,𝑘≤ 3
1 . ∑ ∑ 𝑎 𝑗 𝑎𝑘 [ 𝑃 ( 𝑗 , 𝑘 ) ] =∑ ∑ 𝑎 𝑗 𝑎𝑘 [ 𝑃 ( 𝑗 ,𝑘 ) ] = ∑ 𝑎 𝑗 𝑎𝑘
𝑘 𝑗 𝑗 𝑘 𝑃 ( 𝑗 ,𝑘 )

( )( )
3 3
2. ∑ 𝑎 𝑗 𝑏𝑘= ∑ 𝑎 𝑗 ∑ 𝑏𝑘
1≤ 𝑗 ,𝑘 ≤3 𝑗=1 𝑘=1

( )( )
𝑛 𝑛

∑ 𝑎 𝑗 𝑏𝑘= ∑ 𝑎 𝑗 ∑ 𝑏𝑘
1 ≤ 𝑗,𝑘 ≤ 𝑛 𝑗=1 𝑘=1
𝐹𝑖𝑛𝑑𝑠𝑢𝑚 𝑓𝑜𝑟 :2 ∑ 𝑎𝑘𝑏𝑘
1≤ 𝑗 ,𝑘≤𝑛
1
𝑆 𝑛= ∑ 𝑖𝑛𝑐𝑙𝑜𝑠𝑒𝑑 𝑓𝑜𝑟𝑚
1 ≤ 𝑗, 𝑘≤ 𝑛 𝑘− 𝑗
Prove that closed form of sum of n square is
1
𝑛(𝑛+ 1)( 𝑛+ )
𝑛(𝑛+1)(2 𝑛+1) 2
𝑆 𝑛 =▢𝑛=
2 ∑ 2
𝑘 =
6
=
3
1≤ 𝑘 ≤ 𝑛

Using Induction, Perturbation, Repertoric Method

You might also like