Cheat Sheet - Fundamentos da Ciência da Computação Teórica

Theoretical Computer Science Cheat Sheet Definitions Series fn Ogn iff 3 positive c n0 such that 0 fn cgn n n0 ni1 i nn 12 ni1 i² nn 12n 16 ni1 i³ n²n 1²4 In general ni1 im 1m 1 n 1m1 1 ni1 i 1m1 im1 m 1im fn Ωgn iff 3 positive c n0 such that fn cgn 0 n n0 n1i1 im 1m 1 mk0 m 1 choose k Bk nm1k fn Θgn iff fn Ogn and fn Ωgn Geometric series ni0 ci cn1 1c 1 c 1 i0 ci 11 c i1 ci c1 c c 1 fn ogn iff limn fngn 0 lim n an a iff ε 0 n0 such that an a ε n n0 ni0 i ci ncn2 n 1cn1 cc 1² c 1 i0 i ci c1 c² c 1 sup S least b such that b s s S inf S greatest b such that b s s S Harmonic series liminf an liminfai i n i ni1 1i ni1 iHi nn 12 Hn nn 14 limsup an limsupai i n i ni1 Hi n 1Hn n ni1 i choose m Hi n 1 choose m 1 Hn1 1m 1 n choose k Combinations Size k subsets of a size n set n k Stirling numbers 1st kind Arrangements of an n element set into k cycles 1 n k nn k k 2 nk0 n choose k 2n 3 n k n choose n k n k Stirling numbers 2nd kind Partitions of an n element set into k nonempty sets 4 n k nkk1 5 n k n 1 choose k n 1 choose k 1 n choose m m choose n n choose k n k choose m k 7 nk0 r k choose k r n 1 choose n n k 1st order Eulerian numbers Permutations π1π2πn on 1 2 n with k ascents 8 nk0 n m n 1 m 1 9 nk0 r k s nk r s n n k 2nd order Eulerian numbers 10 n k 1k k n 1 k 11 n 1 n n 1 Cn Catalan Numbers Binary trees with n 1 vertices 12 n 2 2n1 1 13 n k k n1 k n1 k1 14 n 1 n 1 15 n 2 n 1 Hn1 16 n n 1 17 n k n k 18 n k n 1 n1 k n1 k1 19 n n1 n n1 n 2 20 nk0 n k n 21 Cn 1n 1 2n n 22 n 0 n n1 1 23 n k n n1k 24 n k k 1 n1 k n k n1 k1 25 0 k 1 if k 0 0 otherwise 26 n 1 2n n 1 27 n 2 3n n 12n n 1 2 28 xn nk0 n k x k n 29 n m mk0 n k m 1 kn 1k 30 m n m nk0 n k nk k nm 31 n m nk0 n k nk m 1nkm k 32 n 0 1 33 n n 0 for n 0 34 n k k 1 n1 k 2n 1 k n1 k1 35 nk0 n k 2nn2n 36 x xn nk0 n k x n 1 k2n 37 n1 m1 k n k k m k n k k m m 1nk Theoretical Computer Science Cheat Sheet π 314159 e 271828 γ 057721 ϕ 152 161803 ϕ 152 061803 i 2i pi General Probability 1 2 2 Bernoulli Numbers Bi0 odd i 1 Continuous distributions If 2 4 3 B01 B112 B216 B4 130 Pra X b ba px dx 3 8 5 B6 142 B8 130 B10 566 then p is the probability density function of 4 16 7 Change of base quadratic formula X If 5 32 11 logb x loga xloga b b b²4ac2a PrXa Pa 6 64 13 Eulers number e then P is the distribution function of X If 7 128 17 e 1 12 16 124 1120 P and p both exist then 8 256 19 limn 1 xnn ex Pa apx dx 9 512 23 1 1nn e 1 1nn1 Expectation If X is discrete 10 1024 29 1 1nn e 12n 11e24n² O1n3 EgX x gx PrXx 11 2048 31 Harmonic numbers If X continuous then 12 4096 37 1 32 156 13712 4960 36320 761140 71292520 EgX gxpx dx gx dPx 13 8192 41 ln n Hn ln n 1 Variance standard deviation 14 16384 43 Hn ln n γ O1n VARX EX² EX² 15 32768 47 Factorial Stirlings approximation σ VARX 16 65536 53 1 2 6 24 120 720 5040 40320 362880 For events A and B 17 131072 59 n 2πn nen 1 Θ1n PrA B PrA PrB PrA B 18 262144 61 Ackermanns function and inverse PrA B PrA PrB 19 524288 67 aij 2j i1 iff A and B are independent 20 1048576 71 ai1 2 j1 PrAB PrA BPrB 21 2097152 73 αi minj aj j i For random variables X and Y 22 4194304 79 Binomial distribution EX Y EX EY 23 8388608 83 PrX k n k pk qnk q1p if X and Y are independent 24 16777216 89 EX k1n k n k pk qnk np EX Y EX EY 25 33554432 97 Poisson distribution EcX cEX 26 67108864 101 PrX k eλ λkk EX λ Bayes theorem 27 134217728 103 Normal Gaussian distribution PrAiB PrBAi PrAini1 PrAj PrBAj 28 268435456 107 px 12πσ² exμ²2σ² EX μ Inclusionexclusion 29 536870912 109 The coupon collector We are given a Prni1 Xi ni1 PrXi random coupon each day and there are n different types of coupons The distribu nk2 1k1 i1ik Prkj1 Xij 30 1073741824 113 tion of coupons is uniform The expected Moment inequalities number of days to pass before we to col PrX λ EX 1λ lect all n types is PrX EX λ σ 1λ² nHn Geometric distribution PrX k pqk1 q 1 p EX k1 k p qk1 1p Theoretical Computer Science Cheat Sheet Trigonometry Matrices More Trig Multiplication C A B cij nk1 aikbkj Determinants det A 0 iff A is nonsingular det A B det A det B det A π ni1 signπ ai πi 2 2 and 3 3 determinant a b c d ad bc a b c d e f g h i g b c h a c i a b e f d f d e aei bfg cdh ceg fha ibd Permanents perm A π ni1 ai πi Hyperbolic Functions Definitions sinh x ex ex2 cosh x ex ex2 tanh x ex exex ex csch x 1sinh x sech x 1cosh x coth x 1tanh x Identities cosh² x sinh² x 1 tanh² x sech² x 1 coth² x csch² x 1 sinhx sinh x coshx cosh x tanhx tanh x sinhx y sinh x cosh y cosh x sinh y coshx y cosh x cosh y sinh x sinh y sinh 2x 2 sinh x cosh x cosh 2x cosh² x sinh² x cosh x sinh x ex cosh x sinh x ex cosh x sinh xn cosh nx sinh nx n Z 2 sinh² x2 cosh x 1 2 cosh² x2 cosh x 1 θ sin θ cos θ tan θ 0 0 1 0 π6 12 32 33 π4 22 22 1 π3 32 12 3 π2 1 0 in mathematics you dont understand things you just get used to them J von Neumann Law of cosines c² a² b² 2ab cos C Area A ½ hc ½ ab sin C c² sin A sin B2 sin C Herons formula A s sa sb sc s ½ a b c sa s a sb s b sc s c More identities sinx2 1 cos x2 cosx2 1 cos x2 tanx2 1 cos x1 cos x 1 cos xsin x sin x1 cos x cotx2 1 cos x1 cos x 1 cos xsin x sin x1 cos x sin x ei x ei x2i cos x ei x ei x2 tan x iei x ei xei x ei x i e2i x 1e2i x 1 sin x sinhixi cos x cosh ix tan x tanh ix i Pythagorean theorem C² A² B² Definitions sin a AC cos a BC csc a CA sec a CB tan a sin acos a AB cot a cos asin a BA Area radius of inscribed circle ½ AB ABA B C Identities sin x 1csc x cos x 1sec x tan x 1cot x sin² x cos² x 1 1 tan² x sec² x 1 cot² x csc² x sin x cos π2 x sin x sinπ x cos x cosπ x tan x cot π2 x cot x cot π x csc x cotx2 cot x sinx y sin x cos y cos x sin y cosx y cos x cos y sin x sin y tanx y tan x tan y1 tan x tan y cotx y cot x cot y 1cot x cot y sin 2x 2 sin x cos x sin 2x 2 tan x1 tan² x cos 2x cos² x sin² x cos 2x 2 cos² x 1 cos 2x 1 2 sin² x cos 2x 1 tan² x1 tan² x tan 2x 2 tan x1 tan² x cot 2x cot² x 12 cot x sinxy sinxy sin² x sin² y cosxy cosxy cos² x sin² y Eulers equation eix cos x i sin x eiπ 1 v201 1994 by Steve Seiden sseidenacmorg httpwwwcsclsueduseiden Theoretical Computer Science Cheat Sheet Number Theory The Chinese remainder theorem There exists a number C such that C r₁ mod m₁ C rₙ mod mₙ if mᵢ and mⱼ are relatively prime for i j Eulers function ϕx is the number of positive integers less than x relatively prime to x If pᵉⁱ ᵢ1 is the prime factorization of x then ϕx pᵉⁱ¹pᵢ 1 Eulers theorem If a and b are relatively prime then 1 aᵩᵇ mod b Fermats theorem 1 aᵖ¹ mod p The Euclidean algorithm if a b are integers then gcdab gcda mod bb If pᵉⁱ ᵢ1 is the prime factorization of x then Sx ᵈₓ d pᵉⁱ¹¹pᵢ 1 Perfect Numbers x is an even perfect number iff x 2ⁿ¹2ⁿ 1 and 2ⁿ 1 is prime Wilsons theorem n is a prime iff n 1 1 mod n Möbius inversion μi 1 if i 1 0 if i is not squarefree 1r if i is the product of r distinct primes If Ga Fd da then Fa μdG ad Prime numbers pₙ n ln n n ln ln n n n ln ln n ln n O n ln n πn nln n nln n² 2nln n3 O nln n4 Graph Theory Definitions Loop An edge connecting a vertex to itself Directed Each edge has a direction Simple Graph with no loops or multiedges Walk A sequence v₀e₁v₁ eₗvₗ Trail A walk with distinct edges Path A trail with distinct vertices Connected A graph where there exists a path between any two vertices Component A maximal connected subgraph Tree A connected acyclic graph Free tree A tree with no root DAG Directed acyclic graph Eulerian Graph with a trail visiting each edge exactly once Hamiltonian Graph with a cycle visiting each vertex exactly once Cut A set of edges whose removal increases the number of components Cutset A minimal cut Cut edge A size 1 cut kConnected A graph connected with the removal of any k 1 vertices kTough S V S Ø we have k cG S S kRegular A graph where all vertices have degree k kFactor A kregular spanning subgraph Matching A set of edges no two of which are adjacent Clique A set of vertices all of which are adjacent Ind set A set of vertices none of which are adjacent Vertex cover A set of vertices which cover all edges Planar graph A graph which can be embedded in the plane Plane graph An embedding of a planar graph degv 2m vV If G is planar then n m f 2 so f 2n 4 m 3n 6 Any planar graph has a vertex with degree 5 Notation EG Edge set VG Vertex set cG Number of components GS Induced subgraph degv Degree of v ΔG Maximum degree δG Minimum degree χG Chromatic number χₑG Edge chromatic number Gᶜ Complement graph Kₙ Complete graph Kₙ₁ₙ₂ Complete bipartite graph rk ℓ Ramsey number Geometry Projective coordinates triples xyz not all x y and z zero xyz cx cy cz c 0 Cartesian Projective xy xy1 y mx b m 1 b x c 1 0 c Distance formula Lₚ and L metric x₁ x₀² y₁ y₀² x₁ x₀p y₁ y₀p1p lim p x₁ x₀p y₁ y₀p1p Area of triangle x₀ y₀ x₁ y₁ and x₂ y₂ 12 absx₁ x₀ y₁ y₀ x₂ x₀ y₂ y₀ Angle formed by three points 00 x₂ y₂ x₁ y₁ cos θ x₁ y₁ x₂ y₂ ℓ₁ℓ₂ Line through two points x₀ y₀ and x₁ y₁ x y 1 x₀ y₀ 1 x₁ y₁ 1 0 Area of circle volume of sphere A πr² V 43πr³ If I have seen farther than others it is because I have stood on the shoulders of giants Issac Newton Theoretical Computer Science Cheat Sheet π Wallis identity π 22244666 1335577 Brounckers continued fraction expansion π4 1 1²2 3²2 5²2 7²2 Gregorys series π4 1 13 15 17 19 Newtons series π6 12 1232³ 12452⁵ Sharps series π6 17 1 1313 1325 1337 Eulers series π²6 11² 12² 13² 14² 15² π²8 11² 13² 15² 17² 19² π²12 11² 12² 13² 14² 15² Partial Fractions Let Nx and Dx be polynomial functions of x We can break down NxDx using partial fraction expansion First if the degree of N is greater than or equal to the degree of D divide N by D obtaining NxDx Qx NxDx where the degree of N is less than that of D Second factor Dx Use the following rules For a nonrepeated factor NxxaDx Axa NxDx where A NxDx ₓₐ For a repeated factor Nxxam Dx from k0 to m1 Aₖ xamk NxDx where Aₖ 1k dᵏdxᵏ NxDx xa The reasonable man adapts himself to the world the unreasonable persists in trying to adapt the world to himself Therefore all progress depends on the unreasonable George Bernard Shaw Calculus Derivatives 1 dcudx c dudx 2 du vdx dudx dvdx 3 duvdx u dvdx v dudx 4 duⁿdx nuⁿ¹ dudx 5 duvdx vdudx udvdxv² 6 deᶜᵘdx ceᶜᵘ dudx 7 dcᵘdx ln c cᵘ dudx 8 dln udx 1u dudx 9 dsin udx cos u dudx 10 dcos udx sin u dudx 11 dtan udx sec² u dudx 12 dcot udx csc² u dudx 13 dsec udx tan u sec u dudx 14 dcsc udx cot u csc u dudx 15 darcsin udx 11u² dudx 16 darccos udx 11u² dudx 17 darctan udx 11u² dudx 18 darccot udx 11u² dudx 19 darcsec udx 1u1u² dudx 20 darccsc udx 1u1u² dudx 21 dsinh udx cosh u dudx 22 dcosh udx sinh u dudx 23 dtanh udx sech² u dudx 24 dcoth udx csch² u dudx 25 dsech udx sech u tanh u dudx 26 dcsch udx csch u coth u dudx 27 darcsinh udx 11u² dudx 28 darccosh udx 1u² 1 dudx 29 darctanh udx 11 u² dudx 30 darcoth udx 1u² 1 dudx 31 darcsech udx 1u1u² dudx 32 darccsch udx 1u1u² dudx Integrals 1 cu dx c u dx 2 u v dx u dx v dx 3 xⁿ dx 1n1 xⁿ¹ n 1 4 1x dx ln x 5 eˣ dx eˣ 6 dx1 x² arctan x 7 u dvdx dx uv v dudx dx 8 sin x dx cos x 9 cos x dx sin x 10 tan x dx lncos x 11 cot x dx lncos x 12 sec x dx lnsec x tan x 13 csc x dx lncsc x cot x 14 arcsin xa dx arcsin xa a² x² a 0 Theoretical Computer Science Cheat Sheet Calculus Cont 15 arccos xa dx arccos xa a² x² a 0 16 arctan xa dx x arctan xa a2 lna² x² a 0 17 sin² ax dx 12a ax sinax cosax 18 cos² ax dx 12a ax sinax cosax 19 sec² x dx tan x 20 csc² x dx cot x 21 sinⁿ x dx sinⁿ¹ x cos xn n1n sinⁿ² x dx 22 cosⁿ x dx cosⁿ¹ x sin xn n1n cosⁿ² x dx 23 tanⁿ x dx tanⁿ¹ x n1 tanⁿ² x dx n 1 24 cotⁿ x dx cotⁿ¹ xn1 cotⁿ² x dx n 1 25 secⁿ x dx tan x secⁿ¹ xn1 n2n1 secⁿ² x dx n 1 26 cscⁿ x dx cot x cscⁿ¹ xn1 n2n1 cscⁿ² x dx n 1 27 sinh x dx cosh x 28 cosh x dx sinh x 29 tanh x dx ln cosh x 30 coth x dx ln sinh x 31 sech x dx arctanh x 32 csch x dx ln tanh x2 33 sinh² x dx 14 sinh2x 12 x 34 cosh² x dx 14 sinh2x 12 x 35 sech² x dx tanh x 36 arcsinh xa dx x arcsinh xa x² a² a 0 37 arctanh xa dx x arctanh xa a2 ln a² x² 38 arccosh xa dx x arccosh xa x² a² if arccosh xa 0 and a 0 x arccosh xa x² a² if arccosh xa 0 and a 0 39 dxa² x² ln x a² x² a 0 40 dxa² x² 1a arctan xa a 0 41 a² x² dx x2 a² x² a²2 arcsin xa a 0 42 a² x²³² dx x8 5a² 2x² a² x² 3a⁴8 arcsin xa a 0 43 dxa² x² arcsin xa a 0 44 dxa² x² 12a ln a xa x 45 dxa² x²³² xa² a² x² 46 a² x² dx x2 a² x² a²2 ln x a² x² 47 dxx² a² ln x x² a² a 0 48 dxax² bx 1a ln xa bx 49 xa bx dx 23bx 2aa bx³² 15b² 50 a bxx dx 2a bx a 1xa bx dx 51 xa bx dx 12 ln a bx aa bx a a 0 52 a² x²x dx a² x² a ln a a² x²x 53 xa² x² dx 13 a² x²³² 54 x² a² x² dx x8 2x² a² a² x² a⁴8 arcsin xa a 0 55 dxa² x² 1a ln a a² x²x 56 x dxa² x² a² x² 57 x² dxa² x² x2 a² x² a²2 arcsin xa a 0 58 a² x²x dx a² x² a ln a a² x²x 59 x² a²x dx x² a² a arccos x a 0 60 xx² a² dx 13 x² a²³² 61 dxxx² a² 1a ln xa a² x² Theoretical Computer Science Cheat Sheet Calculus Cont Finite Calculus 62 dx xx² a² 1 a arccosa x a 0 63 dx x² x² a² x² a² a² x 64 x dx x² a² x² a² 65 x² a² x⁴ dx x² a²32 3a²x³ 66 dx ax² bx c 1 b² 4ac ln 2ax b b² 4ac 2ax b b² 4ac if b² 4ac 2 4ac b² arctan 2ax b 4ac b² if b² 4ac 67 dx ax² bx c 1 a ln 2ax b 2a ax² bx c if a 0 1 a arcsin 2ax b b² 4ac if a 0 68 ax² bx c dx 2ax b 4a ax² bx c 4ax b² 8a dx ax² bx c 69 x dx ax² bx c ax² bx c a b 2a dx ax² bx c 70 dx xax² bx c 1 c ln 2c ax² bx c bx 2c x if c 0 1 c arcsin bx 2c x b² 4ac if c 0 71 x³ x² a² dx 13 x² 215 a²x² a²32 72 xⁿ sinax dx 1 a xⁿ cosax n a xⁿ¹ cosax dx 73 xⁿ cosax dx 1 a xⁿ sinax n a xⁿ¹ sinax dx 74 xⁿ eax dx xⁿ eax a n a xⁿ¹ eax dx 75 xⁿ lnax dx xⁿ¹ lnax n 1 1 n 1² 76 xⁿ ln axm dx xⁿ¹ n 1 lnaxm m n 1 xⁿ ln axm 1 dx x¹ x¹ x¹ x² x² x¹ x² x¹ x³ x³ 3x² x¹ x³ 3x² x¹ x⁴ x⁴ 6x³ 7x² x¹ x⁴ 6x³ 7x² x¹ x⁵ x⁵ 15x⁴ 25x³ 10x² x¹ x⁵ 15x⁴ 25x³ 10x² x¹ x¹ x¹ x¹ x¹ x² x² x¹ x² x² x¹ x³ x³ 3x² 2x¹ x³ x³ 3x² 2x¹ x⁴ x⁴ 6x³ 11x² 6x¹ x⁴ x⁴ 6x³ 11x² 6x¹ x⁵ x⁵ 10x⁴ 35x³ 50x² 24x¹ x⁵ x⁵ 10x⁴ 35x³ 50x² 24x¹ Difference shift operators Δfx fx 1 fx Efx fx 1 Fundamental Theorem fx ΔFx fxδx Fx C ab fxδx iab1 fi Differences Δcu cΔu Δu v Δu Δv Δuv uΔv EvΔu Δxⁿ nxⁿ¹ ΔHx x¹ Δ2x 2x Δcx c 1cx Δchoosex m choosex m 1 Sums cu δx c u δx u v δx u δx v δx uΔv δx uv EvΔu δx xⁿ δx xn1 m 1 x¹ δx Hx cx δx cx c 1 choosex m δx choosex m 1 Falling Factorial Powers xⁿ xx 1x n 1 n 0 x⁰ 1 xⁿ 1 x 1x n n 0 xnm xm x mn Rising Factorial Powers xⁿ xx 1x n 1 n 0 x⁰ 1 xⁿ 1 x 1x n n 0 xnm xm x mn Conversion xⁿ 1n xn x n 1n 1x 1n xⁿ 1n xn x n 1n 1x 1n xⁿ k1n choosen k xk k1n choosen k 1nk xk xⁿ k1n choosen k 1nk xk xⁿ k1n choosen k xk Theoretical Computer Science Cheat Sheet Series Taylors series fx fa x afa x a² 2 fa i0 x ai i fia Expansions 1 1 x 1 x x² x³ x⁴ i0 xi 1 1 cx 1 cx c²x² c³x³ i0 ci xi 1 1 xⁿ 1 xⁿ x2n x3n i0 xni x 1 x² x 2x² 3x³ 4x⁴ i0 i xi xk dn dxn 1 1 x x 2ⁿ x² 3ⁿ x³ 4ⁿ x⁴ i0 in xi ex 1 x 12 x² 16 x³ i0 xi i ln1 x x 12 x² 13 x³ 14 x⁴ i1 1i1 xi i ln1 1 x x 12 x² 13 x³ 14 x⁴ i1 xi i sin x x 13 x³ 15 x⁵ 17 x⁷ i0 1i x2i1 2i 1 cos x 1 12 x² 14 x⁴ 16 x⁶ i0 1i x2i 2i tan1 x x 13 x³ 15 x⁵ 17 x⁷ i0 1i x2i1 2i 1 1 xn 1 nx nn 1 2 x² i0 n choose i xi 1 1 xn1 1 n1x n2 2 x² i0 i n choose i xi x ex 1 1 12 x 112 x² 1720 x4 i0 Bi xi i 1 2x 1 1 4x 1 x 2x² 5x³ i0 1 i 1 2i choose i xi 11 4x 1 x 2x² 6x³ 1 1 4x 1 1 4x 2xn 1 2 nx 4 n choose 2 x² i0 2i n choose i xi 1 1 x ln 1 1 x 1 2 ln 1 1 x² x 1 x x² Fn x 1 Fn1 Fn1x 1n x² i1 Hi xi i2 Hi1 xi i i0 Fi xi i0 Fni xi Ordinary power series Ax i0 ai xi Exponential power series Ax i0 ai xi i Dirichlet power series Ax i1 ai ix Binomial theorem x yn k0n n choose k xnk yk Difference of like powers xⁿ yⁿ x y k0n1 xn1k yk For ordinary power series α Ax β Bx i0 α ai β bi xi xk Ax ik aik xi Ax k0k1 ai xi xk i0 aik xi Acx i0 ci ai xi Ax i0 i 1 ai1 xi x Ax i1 i ai xi Ax dx i1 ai1 i xi Ax Ax 2 i0 a2i x2i Ax Ax 2 i0 a2i1 x2i1 Summation If bi j0i ai then Bx 1 1 x Ax Convolution Ax Bx i0 j0i aj bij xi God made the natural numbers all the rest is the work of man Leopold Kronecker Theoretical Computer Science Cheat Sheet Series Eschers Knot Expansions 1 1 xn1 ln 1 1 x i0 Hni Hn n i choose i xi 1 xn i0 i choose n xi xn i0 n choose i xi ex 1n i0 i choose n n xi i ln 1 1 xn i0 i choose n n xi i x cot x i0 4i B2i x2i 2i tan x i1 1i 1 22i 2i 1 B2i x2i 1 2i ζx i1 1 ix 1 ζx i0 μi ix ζx 1 ζx i1 ϕi ix ζx p 1 1 px ζ²x i1 di ix where dn d n 1 ζx ζx 1 i1 Si ix where Sn d n d ζ2n 22n 1 B2n π2n 2n n N x sin x i0 1i 1 4i 2 B2i x2i 2i 1 1 4x 2xn i0 n 2i n 1 xi i n i ex sin x i1 2i i1 i1 x2i 1 1 x x i0 4i i2 i12i 1 x2i arcsin x x2 i0 4i i2 i12i 1 x2i Stieltjes Integration If G is continuous in the interval a b and F is nondecreasing then ab Gx dFx exists If a b c then ac Gx dFx ab Gx dFx bc Gx dFx If the integrals involved exist ab Gx Hx dFx ab Gx dFx ab Hx dFx ab Gx dFx Hx ab Gx dFx ab Gx dHx ab c Gx dFx ab Gx dc Fx c ab Gx dFx ab Gx dFx Gb Fb Ga Fa ab Fx dGx If the integrals involved exist and F possesses a derivative F at every point in a b then ab Gx dFx ab Gx Fx dx Cramers Rule If we have equations a11 x1 a12 x2 a1n xn b1 a21 x1 a22 x2 a2n xn b2 an1 x1 an2 x2 ann xn bn Let A aij and B be the column matrix bi Then there is a unique solution iff det A 0 Let Ai be A with column i replaced by B Then xi det Ai det A Fibonacci Numbers 00 47 18 76 29 93 85 34 61 52 86 11 57 28 70 39 94 45 02 63 95 80 22 67 38 71 49 56 13 04 59 96 81 33 07 48 72 60 24 15 73 69 90 82 44 17 58 01 35 26 68 74 09 91 83 55 27 12 46 30 37 08 75 19 92 84 66 23 50 41 14 25 36 40 51 62 03 77 88 99 21 32 43 54 65 06 10 89 97 78 42 53 64 05 16 20 31 98 79 87 The Fibonacci number system Every integer n has a unique representation n Fk1 Fk2 Fkm where ki ki1 2 for all i 1 i m and km 2 1 1 2 3 5 8 13 21 34 55 89 Definitions Fi Fi1 Fi2 F0 F1 1 Fi 1i1 Fi Fi 1 5 ϕi ϕi Cassinis identity for i 0 Fi1 Fi1 Fi² 1i Additive rule Fnk Fk Fn1 Fk1 Fn F2n Fn Fn1 Fn1 Fn Calculation by matrices Fn2 Fn1 Fn1 Fn 0 1 1 1n Improvement makes strait roads but the crooked roads without Improvement are roads of Genius William Blake The Marriage of Heaven and Hell