DHARM52 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
But we formally extend its previous definition to negative arguments by using the
definition of lower factorials, i.e.,
F−
HGI
KJm
n = (– m) (– m – 1) ... (– m – n – 1)/n!
= (– 1)n m (m + 1) ... (m + n – 1)/n!
The expressions m(m + 1) ... (m + n – 1) are called rising factorials of length n and its
value is 1 for n = 0.Since different values derived from numeric function an = m
nF
HGI
KJ
are,mmm m
012 nF
HGI
KJF
HGI
KJF
HGI
KJF
HGI
KJR
S
TU
V
W, , , ............ , ...........Let us assume that A(z) is the generating function of an, i.e.,A(z) = mmz m z m
n
z m
mnmz
01 2F 2
HGI
KJ
+F
HGI
KJ
+F
HGI
KJ
++F
HGI
KJ
+ F
HGI
KJ
...... ... +...
= (1 + z)m= F
HGI
= KJ
kΣm m k
k
0 z
If we put z = 1, i.e.,A(z) =
mmm m
nm
012 mF
HGI
KJ
+F
HGI
KJ
+F
HGI
KJ
++F
HGI
KJ
+ F
HGI
KJ
............ ... +...= F
HGI
KJ
kΣ= =m m m(^0) k
2 ,
and for z = – 1, we have
A(z) =
mmm m
n
m
m
nm
012
F 11
HG
I
KJ
−F
HG
I
KJ
+F
HG
I
KJ
−+−F
HG
I
KJ
++− F
HG
I
KJ
............ ( ) ... ( ) +...
(^) =−F
HG
I
KJ
kΣ= =
m k m
(^0) k
() 10 (for m^ ≥ 1)
EXERCISES
2.1 Let an be an numeric function such that an is equal to the reminder when the integer n is divided
by 17. Let bn be a another numeric function such that is equal to 0 if the integer n is divisible by
3, and is equal to 1 otherwise,- Let cn = an + bn,, then for what values of n, cn = 0 and cn = 1.
- Let dn = anbn,, then for what values of n, dn = 0 and dn = 1.
2.2 Find the generating function for the following discrete numeric functions :
(i) 1, 1, 2, 2, 3, 3, 4, 4, ......................
(ii) 1, 2/3, 3/9, 4/27, .................. ......
(iii) 1, 1 3^0 , 1 3^1 , 1 3^2 , 1* 3^3 , ......
(iv) 3, (3 + 3)–3, (3 + 3^2 )–5, (3 + 3^3 )–5, .........
2.3 Determine generating function and discrete numeric function of the following series :
(i) 2 + 5 + 13 + 35 +.......................