TIGHT BINDING BOOK

PAGES MISSING WITHIN THE BOOK ONLY

CO >

(£< OU_1 64344 >m

26-3-70— 5,000

OSMANIA UNIVERSITY LIBRARY

AcccMionNo. j

Author

_ mis ook should be returnTo^r before the date last marked below.

THE CALCULUS OF FINITE DIFFERENCES

MACM1LLAN AND CO., LIMITED

LONDON BOMBAY CALCUTTA * MADRAS MELBOURNE

THE MACM1LLAN COMPANY

NEW YORK BOSTON CHICAGO DALLAS ' ATLANTA SAN FRANCISCO

THH MACMILLAN COMPANY OF CANADA, L1MITKD

TORONTO

THE CALCULUS

OF

FINITE DIFFERENCES

»Y L. M. MJLNE-THQMSON

MA, K.R.S.E.

ASSISTANT PROfKSSOR OF MATHEMATICS IN THE ROYAL NAVAL COLLKGE, GREENWICH

MACMILLAN AND CO., LIMITED

ST. MARTIN'S STREET, LONDON

1933

F1UNTEI) IN GUJfiAT BRITAIN

PREFACE

THE object of this book is to provide a simple and connected account of the subject of Finite Differences and to present the theory in a form which can be readily applied.

Two distinct reasons impelled me to undertake this work. First, in my lectures at Greenwich to junior members of the Royal Corps of Naval Constructors I have occasion to treat certain aspects of difference equations ; secondly, the calculation of tables of elliptic functions and integrals, on which I have been recently engaged, gave rise to several interesting practical difficulties which had to be overcome. For both these causes my attention has been directed towards the subject and the lack of a suitable text-book upon which to draw was brought to my notice. The only com- prehensive English treatise, namely Boole's Finite Differences, is long since out of print, and in most respects out of date. My first idea was to revise Boole's book, but on looking into the matter it appeared that such a course would be unsatisfactory, if not impracticable. I therefore decided to write a completely new work in which not only the useful material of Boole should find a place, but in which room should also be found for the more modern developments of the finite calculus.

My aim throughout has been to keep in mind the needs of the beginner, so that the book may be regarded as suitable for a first course as well as for more advanced reading. I do not, however, believe that the needs of the beginner in a mathematical subject are best served by eschewing all but the most elementary mathe- matical apparatus. Rather, his interest in the subject may well form an adequate opportunity for enlarging his outlook on the science of mathematics, so that he may the better be enabled to distinguish and appreciate the connection of the whole system and the relative dependency of its several parts. Consequently I have not hesitated to use the mathematical process or terminology which has appeared to me most appropriate to the immediate object in view. On the other hand whenever this course seems to

vi PREFACE

lead beyond the elementary matters, with which all who embark on the»reading of a mathematical book must be presumed to be acquainted, I have included the necessary definitions or proofs as part of the text or have given accessible references to treatises which can ordinarily be found in any mathematical library. In this way it has been possible to treat the subject in a simple yet rigorous manner.

The subject-matter falls naturally into two main divisions which may be subsumed under the headings Interpolation and Difference Equations. The pioneer in interpolation was undoubtedly Briggs, whose work was largely of an arithmetical character. Newton was the originator of the systematic theory and his divided difference formula is really the fundamental basis of all the usual methods of polynomial interpolation. Gregory was probably an independent discoverer in the same field.*

The present work therefore starts with divided differences in Chapter I ; and in a general sense Chapters III, IV and VII may be regarded as elaborations of Newton's work. Chapter V on reciprocal differences, describes a method of interpolation, due to Thiele, by means of rational functions, which is more general than polynomial interpolation, and which will possibly be new to many English readers. Chapter VI introduces the generalisations, due to Norlund, of Bernoulli's polynomials, but here they are treated by a symbolic method, which seemed to me to be as effi- cacious and in many ways more suitable than Norlund's method, which is founded upon a different principle. By means of these generalisations the subject of numerical differentiation and integra- tion assumes a unified aspect which hardly seems to be attainable without them. Chapters I to VII therefore form a suitable intro- ductory course and will make very little demand on the reader's previous mathematical knowledge. I have tried to meet the requirements of those who wish to make numerical applications by giving the formulae in a manner suited to direct use with a table of data. The numerical illustrations scattered through these chapters are mainly of a simple kind which can be easily worked, for it is not my purpose to obscure principles by unnecessary arith- metic. The subject-matter of some of these examples is perhaps

* See H. W. Turnbull, p. 101, footnote.

PREFACE vii

of an unusual nature, but this is intentional in order to lend variety to the applications. In the chapters on Interpolation I have followed Steffensen's excellent example in laying much stress on the remainder term, which measures the error committed in using an interpo- lation formula. Indeed, no formula has been given which is unaccompanied by a means of estimating the remainder.

The part of the book which deals with difference equations begins with Chapter VIII, which expounds Norlund's method of treating the summation problem. Chapter IX applies these methods to elaborating the theory of the Gamma function. In Chapter X, I have attempted to give a consecutive account of the salient properties of factorial series, which, I hope, will prove interesting in itself. The object of this chapter is to develop the properties of the series in which the solutions of difference equations find their natural expression. Chapter XI discusses the difference equation of the first order ; the linear case is completely elucidated, and certain amenable non-linear forms are treated. This chapter includes an investigation of the exact difference equation of the first order. The methods of this, and of succeeding chapters, are illustrated by simple worked examples in the text. Chapter XII considers the properties of the general linear equation, including the application of generalised continued fractions treated by matrix methods. Chapter XIII deals with the important case of constant coefficients. Here the theory is complete, in the sense that the solution can be explicitly obtained. I have dealt with this equation at some length both by Boole's method and by a method of my own, which seems well adapted to applications of a geometrical or physical nature, and which is analogous to Heaviside's method for differential equations. The linear equation with constant coefficients has recently come into prominence in connection with various physical and mechanical problems ; for example in the theory of Structures. Chapters XIV and XVI develop the solution of linear difference equations with variable coefficients by means of Boole's operators, which I have generalised in order to render the treatment more complete. Chapter XV gives an alternative treatment founded on Norlund's use of Laplace's transformation. Chapter XVII gives two fundamental theorems of PoincarS and Perron on the asymptotic properties of the solutions of a certain type of linear difference equation. The proof of Perron's theorem

viii PREFACE

is made to depend upon the properties of a certain class of simul- taneous linear equations in infinitely many unknowns. The theory is so interesting and so closely connected with finite differences that it has seemed worth while to give Perron's treatment in extenso.

Operational and symbolic methods have been freely used through- out the book, and it is hoped that the manner of presentation here given will be found free from the objections often associated with their use. Indeed it has always seemed to me that symbolic methods constitute the essence of the finite calculus. My choice of notations has therefore been made with a view to facilitating the statement and application of operational methods, and to stressing the analogies with the infinitesimal calculus.

In stating theorems I have as far as possible associated the name of the discoverer as sufficient indication of the origin, but it must not be assumed that the method of presentation is in every case that in which the theorem was originally given. Indeed in the case of the work of the older analysts it would be easy, but un- profitable, to point out defects and lack of rigour in many of their proofs.

My labour in correcting the proof sheets has been greatly lightened by Professor H. W. Turnbull, F.R.S., who has read the first proof and made many valuable suggestions both mathematical and historical ; and by Dr. A. C. Aitken, F.R.S.E., who has performed the same kindly office, has supplied many original examples, and has verified the numerical work. To both these friends I wish to express my lively thanks for assistance which has helped me to remove many imperfections both of expression and demonstration. For any blemishes which may remain I am solely responsible, but I am led to express the hope that the work will be found to be free from important errors. I take this opportunity of expressing my thanks to the officials of the Glasgow University Press for the ready way in which they have met my somewhat exacting require- ments.

L. M. MILNE-THOMSON.

MATHEMATICS DEPARTMENT, ROYAL NAVAL COLLEGE, GREENWICH, July 1933.

CONTENTS

PAGK

INTRODUCTION xxi

NOTATIONS xxii

CHAPTER I DIVIDED DIFFERENCES

1-0. Definitions 1

1-1. Newton's interpolation formula with divided differences - - 2

1-16. Rolle's Theorem 4

1-2. Remainder term in Newton's formula ..... 5

1-3. Divided differences are symmetric functions of the arguments 7

1-31. Divided differences of xn - 7

1-4. Lagrange's interpolation formula 8

1-5. Expression of divided differences by means of determinants - 9

1-6. Divided differences expressed by definite integrals 10

1-7. Divided differences expressed by contour integrals - - - 11

1-8. Divided differences with repeated arguments 12

1-9. Interpolation polynomials 14

EXAMPLES I ---------- 17

CHAPTER II DIFFERENCE OPERATORS

2-0. Difference notation ........ 20

2-01. Central difference notation ------- 22

2-1. Difference quotients 23

2-105. Partial difference quotients 24

2-11. Difference quotients of factorial expressions 25

2-12. Expansion of a polynomial in factorials 27

2-13. Successive difference quotients of a polynomial 28

2-14. Difference quotients of ax 29

2-2. Properties of the operator A - - - - - - - 30

<•>

2-3. The operator y 31

b ix

x CONTENTS

PAGE

24. The operator Ew 31

2-41. Herschel's Theorem 32

242. ^(E")ajr = a*^(O 32

243. <£(£")«*« (*) = a" <Mow £*>(*) 32

2-5. Relations between A, E", # 33

4l>

2-51. The analogue of Leibniz' Theorem 34

2-52. Difference quotients of axvx 35

2-53. Difference quotients of zero 36

2-54. Difference quotients in terms of derivates 37

2-6. The summation operator p"1 37

2-61. A theorem on the value of p^1 ut 39

2-62. Relation between sums and functional values 39

2-63. Moments 40

2-64. Partial summation 41

2-7. Summation of finite series 42

2-71. Summation of factorial expressions of the form x(m) - - 42

2-72. Polynomials 43

2-73. Factorial expressions of the form x(~m) 44

2-74. A certain type of rational function ------ 45

2-75. The form ax </>(#), <t>(x) a polynomial 46

2-76. The form vx<j>(x), <£(#) a polynomial 46

2-77. Unclassified forms 48

EXAMPLES II 49

CHAPTER III INTERPOLATION

3-0. Divided differences for equidistant arguments .... 56

3-1. Newton's interpolation formula (forward differences) - - 57

3-11. Newton's interpolation formula (backward differences) - - 59

3-12. The remainder term 61

3-2. Interpolation formulae of Gauss ------ 63

3-3. Stirling's interpolation formula 67

34. Bessel's interpolation formula 68

341. Modified Bessel's formula 71

3-5. Everett's interpolation formula 72

3-6. Steffensen's interpolation formula 74

3-7. Interpolation without differences 75

3-81. Aitken's linear process of interpolation by iteration - - 76

3-82. Aitken's quadratic process 78

3'83. Neville's process of iteration 81

EXAMPLES III 84

CONTENTS xi

CHAPTER IV NUMERICAL APPLICATIONS OF DIFFERENCES

PAGE

4-0. Differences when the interval is subdivided 87

4-1. Differences of a numerical table ...... 88

4-2. Subtabulation 91

4-3. Inverse interpolation ........ 95

4-4. Inverse interpolation by divided differences .... 96

4'5. Inverse interpolation by iterated linear interpolation - - 97

4-6. Inverse interpolation by successive approximation 99

4-7. Inverse interpolation by reversal of series - - - - 100

EXAMPLES IV 101

CHAPTER V RECIPROCAL DIFFERENCES

5-1. Definition of reciprocal differences ------ 104

5-2. Thielo's interpolation formula - - - - - - -106

5-3. Matrix notation for continued fractions - - - - 108

5-4. Reciprocal differences expressed by determinants - - 110

5-5. Reciprocal differences of a quotient - - - - - 112

5-6. Some properties of reciprocal differences - - - - 114

5-7. The remainder in Thielo's formula - - - - - - 116

5*8. Reciprocal derivates ; the confluent case - - - - 117

5-9. Thielo's Theorem 119

EXAMPLES V 122

CHAPTER VI THE POLYNOMIALS OF BERNOULLI AND EULER

6-0. The </> polynomials 124

6-01. The p polynomials 126

6-1. Definition of Bernoulli's polynomials 126

6-11. Fundamental properties of Bernoulli's polynomials - - - 127

6-2. Complementary argument theorem 128

6-3. Relation between polynomials of successive orders - - - 129

6-4. Relation of Bernoulli's polynomials to factorials - - - 129

6-401. The integral of the factorial 131

6-41. Expansion of x(n) in powers of x 133

6-42. Expansion of xv in factorials - - - - - - 133

6-43. Generating functions of Bernoulli's numbers - - - 134

xii

PAG]

6-5. Bernoulli's polynomials of the first ordefN^^^ 136

6-501. Sum of the vth powers of the first n integers*1 - 137

6-51. Bernoulli's numbers of the first order - 137

6*511 . Euler-Maclaurin Theorem for polynomials - 139

6-52. Multiplication Theorem 141

6-53. Bernoulli's polynomials in the interval (0, 1 ) - 141

6-6. The 73 polynomials --------- 142

6-7. Definition of Euler's polynomials ------ 143

6'71. Fundamental properties of Euler's polynomials - - - 144

6-72. Complementary argument theorem .... - 145

6-73. Euler's polynomials of successive orders - 145

6-8. Euler's polynomials of the first order 146

6-81. Euler's numbers of the first order 147

6*82. Boole's Theorem for polynomials 149

EXAMPLES VI 150

CHAPTER VII NUMERICAL DIFFERENTIATION AND INTEGRATION

7-0. The first order derivate 154

7-01. Derivates of higher order - - 155

7-02. Markoff's formula 157

7-03. Derivates from Stirling's formula ------ 159

7-04. Derivates from Bessel's formula ------ 161

7-05. Differences in terms of derivates - - - - - - 162

7-1. Numerical integration - - - - - - - - 162

7-101. Mean Value Theorem 163

7-11. Integration by Lagrange's interpolation formula - - - 164

7-12. Equidistant arguments 165

7-13. Remainder term, n odd - - - - - - - - 166

7-14. Remainder term, n even - - - - - - - 167

7-2. Cotes' formulae 168

7-21. Trapezoidal rule 170

7-22. Simpson's rule 171

7-23. Formulae of G. F. Hardy and Weddle 171

7-3. Quadrature formulae of the open type 172

7-31. Method of Gauss 173

7-33. Method of Tschebyscheff 177

7-4. Quadrature formulae involving differences - - - - 180

7-41. Laplace's formula 181

7-42. Laplace's formula applied to differential equations - - - 183

7-43. Central difference formulae 184

CONTENTS xiii

PAGE

7-5. Euler-Maclaurin formula - 187

7-51. Application to finite summation - - - 191

7-6. Gregory's formula 191

7-7. Summation formula of Lubbock - - - - - 193

EXAMPLES VII 196

CHAPTER VIII THE SUMMATION PROBLEM

8-0. Definition of the principal solution or sum - 201

8-1. Properties of the sum -------- 204

8-11. Sum of a polynomial -------- 208

8-12. Repeated summation 208

8-15. Proof of the existence of the principal solution (real variable) - 209

8-16. Bernoulli's polynomials Bv (x \ co) 213

8-2. Differentiation of the sum - - - - - - 213

8-21. Asymptotic behaviour of the sum for large values of x - - 214

8-22. Asymptotic behaviour of the sum for small values of co - - 216

8-3. Fourier series for the sum ....... 218

8-4. Complex variable. Notation. Residue Theorem - - - 220

8-41. Application of Cauchy's residue theorem .... 222

8-5. Extension of Jhe theory 226

8-«53. The sum of the exponential function - - - - 231

8-6. Functions with only one singular point ----- 232

8-7. An expression for F (x \ -co) 238

EXAMPLES VI11 238

CHAPTER IX THE PSI FUNCTION AND THE GAMMA FUNCTION

9-0. The function^' (x \ co) 241

9-01. Differentiation of the Psi function ------ 241

9-03. Partial and repeated summation 243

9-1. Asymptotic behaviour for large values of # . . . 244

9-11. Partial fraction development of ^ (x \ co ) - ... 245

9-2. Multiplication theorem for the Psi function - ... 246

9-22. Fourier series for ¥ (x) 247

9-3. Gauss' integral for ¥ (x) 247

9-32. Poisson's integral 248

9-4. Complementary argument theorem for the Psi function - - 249

9-5. The Gamma function 249

xiv CONTENTS

PAGE

9-52. Schlomilch's infinite product for F(x + l) - 250

9-53. Infinite products expressed by means of T (x) ... 251

9-54. Complementary argument theorem for T (x) - - - - 251

9-55. The residues of T (a;) 252

9-56. Determination of the constant c 252

9-6. Stirling's series for log T (x +h) 253

9-61. An important limit 254

9-66. Generalised Gamma function T (x \ co) 255

9-67. Some definite integrals 256

9-68. Multiplication theorem of the Gamma function - - - 257

9-7. Euler's integral f or T (x) 257

9-72. Complementary Gamma function Tl (x) 258

9*8. Hypergeometric series and function F (a, b ; c ; x) - - - 260

9-82. Hypergeometric function when x = 1 261

9-84. The Beta function B(#, y) 262

9-86. Definite integral for the hypergeometric function - - - 264

9-88. Single loop integral for the Beta function .... 265

9-89. Double loop integral for the Beta function .... 266

EXAMPLES IX 267

CHAPTER X FACTORIAL SERIES

10-0. Associated factorial series 272

10-02. Convergence of factorial series 273

10-04. Region of convergence 275

10-06. Region of absolute convergence 276

10-07. Abel's identities 276

10-08. The upper limit of a sequence 277

10-09. Abscissa of convergence. Landau's Theorem - - - 279

10-091. Ma jorant inverse factorial series 283

10-1. Series of inverse factorials 284

10-11. Uniform convergence of inverse factorial series - - - 284

10-13. The poles of 12 (x) 287

10-15. Theorem of unique development 288

10-2. Application of Laplace's integral ; generating function - - 288

10-22. Order of singularity and the convergence abscissa - - - 292

10-3. The transformation (x, x +m) 293

10-32. The transformation (x, a:/co) 294

10-4. Addition and multiplication of inverse factorial series - - 295

10-42. Differentiation of inverse factorial series .... 297

1043. An asymptotic formula 298

CONTENTS xv

PAGE

1044. Integration of inverse factorial series 299

10-5. Finite difference and sum of factorial series .... 300

10-6. Newton's factorial series 302

10*61. Uniform convergence of Newton's series 302

10-63. Null series 304

10-64. Unique development 305

10-65. Expansion in Newton's series ; reduced series - 306

10-67. Abscissa of convergence of Newton's series .... 309

10-7. Majorant properties 310

10-8. Eulcr's transformation of series 311

10-82. Generating function 312

10-83. Laplace's integral and Newton's series 314

10-85. Expansion of the Psi function in Newton's series - - - 315

10-9. Application to the hypergeometric function - - - 316

EXAMPLES X 317

CHAPTER XI THE DIFFERENCE EQUATION OF THE FIRST ORDER

11-0. Genesis of difference equations 322

11-01. The linear difference equation of the first order - - - 324

11-1. The homogeneous linear equation 324

11-2. Solution by means of the Gamma function. Rational cocllicients 327

11-3. Complete linear equation of the first order .... 328

11-31. The case of constant coefficients 329

11-32. Application of ascending continued fractions ... - 330

11-33. Incomplete Gamma functions 331

11-34. Application of Prym's functions 332

1 1 -4. The exact difference equation of the first order - - - 334

11-41. Multipliers 339

11-42. Multipliers independent of x 339

11-43. Multipliers independent of u 340

11-5. Independent variable absent. Haldane's method - - - 341

11-51. Boole's iterative method 343

11*6. Solution by differencing. Clairaut's form .... 344

11-7. Equations homogeneous in u 346

11-8. Riccati's form 346

11-9. Miscellaneous forms 347

EXAMPLES XI 348

xvi CONTENTS

CHAPTER XII

GENERAL PROPERTIES OF THE LINEAR DIFFERENCE EQUATION

PAGE

12-0. The homogeneous linear difference equation - - - -351

12-01. Existence of solutions 352

12-1. Fundamental system of solutions 353

12-11. Casorati's Theorem 354

12-12. Heymann's Theorem 357

12-14. Relations between two fundamental systems .... 359

12-16. A criterion for linear independence 360

12-2. Symbolic highest common factor 361

12-22. Symbolic lowest common multiple 363

12-24. Reducible equations 366

12-3. Reduction of order when a solution is known .... 367

12-4. Functional derivates 369

12-5. Multiple solutions of a difference equation .... 370

12-6. Multipliers. Adjoint equation 372

12-7. The complete linear equation. Variation of parameters - - 374

12-72. Polynomial coefficients 377

12-8. Solution by means of continued fractions .... 378

EXAMPLES XII 381

CHAPTER XIII

THE LINEAR DIFFERENCE EQUATION WITH CONSTANT COEFFICIENTS

13-0. Homogeneous equations 384

13-02. Boole's symbolic method 387

13-1. Complete equation 388

13-2. Boole's operational method - - 392

13-21. Case I, <j>(x) = xm 393

13-22. Case II, <f>(x) = ax 396

13-23. Caselll, </> (x) = axR (x) 398

13-24. The general case 398

13-25. Broggi's method for the particular solution .... 401

13-26. Solution by undetermined coefficients 403

13-3. Particular solution by contour integrals 404

13-32. Laplace's integral 407

13-4. Equations reducible to equations with constant coefficients - 408

CONTENTS xvii

PAGE

13-5. Milne-Thomson's operational method 410

13-51. Operations on unity 411

13-52. Operations on a given function X 412

13-53. Application to linear equations witli constant coefficients - 413

13-54. Simultaneous equations 415

13-55. Applications of the method - - 415

13-6. Simultaneous equations 420

13-7. Sylvester's non-linear equations 420

13-8. Partial difference equations with constant coefficients - - 423

13-81. Alternative method 425

13-82. Equations resolvable into first order equations - - - 426

13-83. Laplace's method 427

EXAMPLES XIII 429

CHAPTER XIV

THE LINEAR DIFFERENCE EQUATION WITH RATIONAL COEFFICIENTS. OPERATIONAL METHODS

14-0. The operator p 434

14-01. The operator n 436

14-02. Inverse operations with TT 437

14-03. The operators ni9 pA 439

14-1. Theorem I 439

14-11. Theorem II 440

14-12. Theorem III 440

14-13. Theorem IV 442

14-14. Theorem V 443

14-2. Formal solution in series 445

14-21. Solution in Newton's series 448

14-22. Exceptional cases 451

14-3. Asymptotic forms of the solutions 457

14-31. Solutions convergent in a half-plane on the left - - - 459

14-4. The complete equation 460

14-5. Monomial difference equations 461

14-6. Binomial equations 465

14-7. Transformation of equations. Theorems VI, VIT, VIII - - 467

14-71. Equation with linear coefficients 469

14-73. Theec{ua,tioTL(ax*+bx+c)u(x)+(ejc+f)u(x-l)+gu(x-2) = 0 472

2

14-75. The equation (ax2 + bx +c) Aw +(ex +f) Aw +gu - 0 - - - 474

14-8. Bronwin's method 475

14*9. Linear partial difference equations 475

xviii CONTENTS

PAGE

1 4-91 . Laplace's method for partial equations 476

EXAMPLES XIV 477

CHAPTER XV

THE LINEAR DIFFERENCE EQUATION WITH RATIONAL COEFFICIENTS. LAPLACE'S TRANSFORMATION

15-0. Laplace's transformation 478

15-1. Canonical systems of solutions 482

15-2. Factorial series for the canonical solutions .... 485

15-3. Asymptotic properties , - 487

15*31. Casorati's determinant 488

15-4. Partial fraction series 490

15-5. Laplace's difference equation 491

15-51. Reducible cases 493

15-52. Hypergeometric solutions - 494

15-53. Partial fraction series 495

15-54. Relations between the canonical systems 496

15-55. The case a^ =a2 498

15-6. Equations not of normal form 500

EXAMPLES XV 501

CHAPTER XVI

EQUATIONS WHOSE COEFFICIENTS ARE EXPRESSIBLE BY FACTORIAL SERIES

16-0. Theorem IX 504

16-01. Theorem X 505

16-1. First normal form 508

16-2. Operational solution of an equation of the first normal form - 509

16-3. Convergence of the formal solution 511

16-4. Example of solution - - - - - - - 516

16-5. Second normal form 518

16-6. Note on the normal forms 519

EXAMPLES XVI 521

CHAPTER XVII THE THEOREMS OF POINCARfi AND PERRON

17-0. The linear equation with constant coefficients - 523

17-1. Poincari's Theorem 526

CONTENTS xix

PAGE

17 -2. Continued fraction solution of the second order equation - - 532

17-3. Sum equations 534

17-4. Homogeneous sum equations with, constant coefficients.

Theorem I 537

17-5. A second transformation of sum equations .... 539

17-6. General solution of sum equations. Theorem II 542

17-7. Difference equations of Poincare's type. Perron's Theorem - 548

EXAMPLES XVII 550

INDEX 553

INTRODUCTION

LET f(x) be a given function of the variable x. The Differential Calculus is concerned with the properties of

which is still a function of the single variable x. On the other hand the Calculus of Differences is concerned with the properties of

CO

which is a function of the two variables x and o>.

More generally, in contrast with the Infinitesimal Calculus, the Finite Calculus is concerned with the values of a function at a set of isolated points and with such properties as may be derivable there- from.

Suppose then that we are given the numbers f(xl),f(x2),f(x^)9 ... , and an argument x different from XL, x2) x3, ... . Among the subjects of enquiry which naturally present themselves are the following.

(i) The determination of f(x) from the given functional values. This is the Interpolation problem.

(ii) The determination of

/'(*), \bfWdx.

J a

These are the problems of Numerical Differentiation and Integration. Extending our enquiries in another direction we are led to con- sider the properties of the functions f(x) denned by the equation

where g(x) is a given function. This constitutes the Summation problem, which is analogous to the problem of integration in the Integral Calculus.

xxii INTRODUCTION

On the theory of summation we are able to found in a satisfactory manner the theory of the Gamma function which plays such an important part in the Calculus of Differences.

Consideration of more general relations between /(#),/(# -f-co), ... , /(x-f-nco) brings us to the study of difference equations, which are analogous to the differential equations of the Infinitesimal Calculus.

NOTATIONS

THE following list, which is intended only for reference, contains the symbols, operators, and functions which occur most frequently in this book. The numbers refer to the sections where explanations are given.

SYMBOLS

(m\ __ m(m- 1) ._. . (m-n+ 1) \n)~ nT '

lim f(x), the limit of f(x) when

x~*a x tends to a.

lim sup xn, Upper limit, 10-08.

n-»-oo

f(x) ~ g(x), 8-22.

==, symbolic equivalence, 2-41.

R(x), the real part of #, 84.

Rn(%)> Rn, Remainder Terms, 1-1, 7-11.

| a? |, argz, 8-4.

or, Arbitrary Periodic Function, 11-1.

... xn], Divided Difference, 1-0.

= x(x - co) (x - 2co) . . . (#- wco + co), 2-11.

co)-1, 2-11.

n

A0m, Difference Quotient of w Zero, 2-53.

Bernoulli's Numbers of order n, 6-1. ), Euler's Numbers of order n,

6-7,

Bv, Bernoulli's Numbers, 6-5. EV) Euler's Numbers, 6-8. 0(zn), 9-8.

D,

Ax

"

V,

Difference Operator, 2-0. {JL§, Central Difference Oper-

ators, 2-01.

Difference Quotient Oper-

ator, 2-1.

Differentiation Operator, 2-1. > Partial Difference Quotient,

2-105. 2-3.

NOTATIONS xxiii

OPERATORS

E", 2-4.

p-1, Summation Operator, 2-6. p, pn, Reciprocal Difference, 5-1. r, rn, Reciprocal Derivate, 5-8.

, Sum Operator, 8-0.

TC, p, 14-01, 14-0. TC,, plf 14-03.

FUNCTIONS ex, exp x, Exponential Function.

Bin\x), Bernoulli's Polynomial of order n, 6-1.

Bv(x\ co), Generalised Bernoulli's Polynomial, 8-16.

E^\x)9 Euler's Polynomial of order n, 6-7.

Bv(x\ Bernoulli's Polynomial, 6-5.

Ev(x), Euler's Polynomial, 6-8.

Pm(x), Periodic Bernoulli Func- tion, 7-5.

B(z, y), Beta Function, 9-84 r(x), Gamma Function, 9-5. rl(x), Complementary Gamma

Function, 9-72. r(x|d)), Generalised Gamma

Function, 9-66. ^(x | co), Psi Function, 9-0. ¥(x), Psi Function, 9-0. F(x\ co), Sum Function, 8-0. F(a, b ; c ; x), Hypergeometric

Function, 9-8. Q(ic), Factorial Series Sum

Function, 10-1.

M] DIVIDED DIFFERENCES

or

f(x) = f(xj + (x - a^) [x^2] + (x- xj (x -

+ (x-x1)(x-x2)...(x-xn)[xx1x2...xn], or

(1) /(z)=/(ZiH2(z-*i)(z^

*-l

(2) where Rn (x) = (x - x^ (x - x2) . . . (x - xn) [xx^2 . . . xn].

This is Newton's general interpolation formula with the remainder term Rn(x). The formula is of course a pure identity and is therefore true without any restriction on the form of f(x).

By means of this formula the evaluation of a f unction /(x) whose value is known for the values xl9 x2, ... , xn of the variable is reduced to the problem of evaluating the remainder term Rn (x). Should this term be known or negligible, the required value/(#) can be calculated from Newton's formula.

It should be observed that no particular rule is laid down for the sequence of the arguments x, xv x2, ... " xn, which need not be in ascending or descending order of magnitude.

Iff(x) be a polynomial of degree n 1 in x, then

x-xl

is of degree n - 2 in x. Hence the operation of taking the divided difference of a polynomial lowers the degree by unity. Conse- quently the divided difference of the (n - 1 )th order of a polynomial of degree n - 1 is constant, and therefore the divided difference of the nth order is zero, that is, [xx± ... xn] 0.

In this case En(x) == 0, so that the value of f(x) given by the formula

n-l

(3) f(x) = f(xj + ^l(x-x1)...(x- xa) [X& . . . xs+l]

*=--!

is exact.

Iff(x) be not a polynomial, we see that

Rn(x) = 0, for x = xl9 x2, ... , xn,

4 DIVIDED DIFFERENCES [1-1

so that the right-hand member of (3) yields the polynomial of degree n~ 1 whose value coincides with the value of f(x) for

X = a?j_, XZi •• , Xn.

Example. Find approximately the real root of the equation «

y3-2y-5 = 0. Let x = y3 - 2y - 5.

This relation defines a function y~f(x). We want the value of /(O). Attributing suitable values to y we obtain the folio wfng table of divided differences.

x f(x)

-1-941 1-9

+ •10627 -1-000 2-0 --0060

+ 09425 + -0005

+ 0-061 2-1 --0044

+ -08425 +-0003

+ 1-248 2-2 --0034

+ -07582 + 2-567 2-3

Thus approximately, using (3) above, we have y = 2-0+ 1 x -09425 + 1 x -061 x -0044 + 1 x -061 x 1-248 x -0003 = 2-09454.

The corresponding value of a? is - 0-00013 and the above value of y is in error by about one unit in the last digit.

1 -15. Rolle's Theorem. In order to discuss the form of the remainder term in Newton's formula we need the following theorem known as Rolle's theorem.

If the function f(x) be continuous and differentiate in the interval a^x^ib, where a, b are two roots of the equation f(x) = 0, then the equation f (x) = 0 has at least one root interior to the interval (a, b).

Proof. If f(x) have the constant value zero, the theorein is evident. If f(x) be not constantly zero, it will take positive values pr negative values. Suppose that f(x) takes positive values. r£hen

1-15] DIVIDED DIFFERENCES , 5

f(x) being continuous will attain a maximum value M for some point £ such that a < £ < b. Thus, if h be positive,

h

is negative or zero and hence the limit when A->0, namely /'(!•), cannot be a positive number, that is,

Similarly, by considering the ratio

we prove that

/'(5)>o.

Thus we have /'(£) = 0 and the theorem is proved. In the same way we prove the theorem for the case when f(x) takes negative values.

1 *2. The Remainder Term. From 1-1 (2), we have

n-l

where Pn _x (a;) = f(xj -f X (x - xi) - - (x ~ x*) lxixz xs+i\>

*-i

so that Pn-i(x) is a polynomial of degree w-1, and its (w-l)th derivate is

(1) P<tf>(x) = (n-l)\[x1xt...xn].

Hitherto f(x) has been unrestricted. We now suppose that in the interval .(a, 6) bounded by the greatest and least of x, xv x2, ... , xn the function f(t) of the real variable ty and its first n-l derivates are finite and continuous and that/<n)(£) exists.

Then since Rn(t) vanishes when t = xvx2,...9 xn, by Rolle's theorem it follows that Rn (t) vanishes at n 1 points of (a, b) and therefore by a second application of the theorem that Rn (t) vanishes at w-2 points of (a, 6). Proceeding in this way we see that fifi1"" r*(>j) = 0 where TJ is some point of (a, b).

Thus /*-1>)--Pfcri1)) = 0,

6 DIVIDED DIFFERENCES [1-2

so that

(2) [Xix2 ••• xn\ ~ /n~~ j\j 9

which is a formula expressing the divided difference of order n 1 in terms of the (n-l)th derivate of f(x) at some point of (a, b). Hence we have

[xx^... xn\ j , where £ is some point of (a, 6). We have therefore

W\ 7? (r\ (r Y \ (T Y \ (v T \ ^ ^'

\°) l\,n\JU) {JU JU^^Ji d,%) ... \Jb xn) ™t '

where ^ is some point of (a, 6).

This important result enables us to find an upper limit to the error committed in omitting the remainder term, provided that we can find an upper limit for the nth derivate off(t) in the interval bounded by the greatest and least of x, xv x2, ... , xn.

Example. Find an approximate value of Iog10 4-01 from the following table :

X

Iog10 x

4-0002

0-6020 817

+• 108431

4-0104

•6031 877

-•0136

+ •108116

4-0233

•6045 824

- -0130

+ -107869

4-0294 -6052 404

The divided differences are as shewn. Thus approximately

log 4-01 = -6020817 + -0098 x -108431 + -0098 x -0004 x -0136 = -6031444,

which is correct to seven places.

The error due to the remainder term is of order

-0098 x -0004 x -0133 x -4343 x 2

1-2] DIVIDED DIFFERENCES 7

where x varies between 4-0002 and 4-0294, which is less than 2 in the 10th decimal place. The above value could therefore be affected only by errors of rounding in the seventh place.

1-3. The Divided Differences are Symmetric Functions of the Arguments. By definition

L XJ ,~, /y, fy> iy

Jj ~~~ tAS-t JU-t Jj

so that we obtain without difficulty

\XX X 1 - /^ 4- /to) _ 4. __

I t«/vt'|*C'9 I , k y » ~ , . / \ I /

•*• ** ( T />>ll/y* T*l I'T* T\ ( T T* I i/>*

Idly *t/i I I«A/ "~~ ^O/ \ 1 / V 1 "~~ 2/ \ 2 **

It is now very easily proved by induction that

l~\\ f ' VTf T* 1* 1 *

i A y I A/A/-* a/0 «*/fi I

f /.v-X f/^v. \

/W L J\Xl)

~~ ~ . ~t~

(x-x1)(x-x2)...(x-xn) (X1-x)(x1-x2)...(x1-xn)

+ .._. /to)

(xn - x) (xn -xj... (xn - xn_r) '

Clearly the interchange of any two of the arguments does not alter the value of the divided difference, which is therefore a symmetric function of its n arguments.

For example [^^2] [^r*^] ~ [#2X;ril- Again [x^xz . . . «n_txwxn+1] = [xnxzx3 . . . xn,^xn+l} , so that

~~ x

n+l

xn ~~ xn {-I

1-31. The divided differences of xn can be obtained as follows : from 1-3 (1),

1H 1 ^ n

f -1 (Xs ~ Xl) (X8 ~~X2/ to •" ^p

8 DIVIDED DIFFERENCES [1-31

This last is the coefficient of tn~p in the expansion of

^ _ *.* ._ _____

/u (x, - za) . . . (xt - x^) (1 - xtt) (xs - XM) . . . (x. - xp+l)

But this expression is evidently the result of putting into partial fractions the function

and hence * the coefficient of tn~p is the sum of the homogeneous products of degree n-p of xv x2, ... , xp+l.

Thus [x±x2 . . . xv+I] = S Xj°l x2a* . . . xpa%i l,

where the summation is extended to all positive integers including zero which satisfy the relation al + a2+ ... +aphl n-p.

For the divided differences of - we have

x

and this is the value when t = 0 of

1

which is obtained by putting into partial fractions

- 1

so that

(-1)"

~

1*4. Lagrange's Interpolation Formula. From 1-3 (1) we have

m fix\

(1) /(*)

.ti\ (x-x1)(x

-a,)". (xz-xn) - ,

where Rn (x) = (x-x1)(x-x2) ... (x- xn) [xx±x2 . . . xn].

*G. Chrystal, Algebra, 2nd edition, (London, 1919), 205.

1-4] DIVIDED DIFFERENCES 9

This is Lagrange's Interpolation Formula with the remainder term Rn(x). Comparing with 1-1 (2) we see that this remainder term is the same as the remainder term in Newton's Formula. It follows that Lagrange's Formula has exactly the same range of application as Newton's and yields identical results.

The formula may also be written in a slightly different form. Write (2) <£(z) = (x-x1)(x-x2)...(x-xn).

/Q\ TU^*, ft™\ \.^ J \ S/ T\ / i TJ /,«\

(o) xnen T\X) -— / t ~ ~~j~» ~r jLi>n(X).

1 *5. Expression of Divided Differences by means of Deter m i nants. By a well-known theorem in determinants origin- ally due to Vandermonde and generalised by Cauchy, we have

(1)

1