Summation of series has the same exponent and the base numbers.doc

Summation of series has the same exponent and the base numbers in a arithmetic progression in computational complexityLiu Ai-Jun Fan Jing-Bo Yu Xian-Feng Department of computer science, ShangLuo University, ShangLuo, China, 726000Abstract: The computers advantage lies in its automation, Problem that can be solved by algebra can also be realized through programming. Once the problem can use program solved, there will only be input and output. Algorithm quality mainly lies in the computational complexity. So complexity always is one of research hot spot problems of computer science. During complexity calculation process will often meet a problem that calculating the summation of a series has the same exponent and its base number is a arithmetic progression. The article start from a simple problem , give several methods to solve the problem, and spread the problems to their general case. Keywords: complexity; series; crack term; undetermined coefficient1 ProblemTalk from a simple complexity calculation problem, the problem1 is calculating the execution number of x=x+1 in the following program. for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x=x+1;Remember the execution times of x=x+1 as then, () Definition 1 Form if ，is a problem that summation of series has the same exponent and the base number is a arithmetic progression in computational complexity(Simple notes for SBACC).Proposition 1 In nature, analogously ， are all SBACCs.For example, ，Proof We say is also a SBACC because, ,So can be divided into SBACCs and . Generally, ,So analogously ， are all SBACCs. Proposition 1 is reasonable.2 Several methods to solve the problem 2.1 Rise the exponent to spread and offset under dislocationIf we can calculate () (2), then we will get the solution of . Put both sides together, each equation on the left will offset with the first term in the previous equation on the right. () Calculate from ()(1) we get, ()Push () into () (3) get, .Similarly, can be calculated as follow,Offset under dislocation2 each equation on the left offset with the first term in the previous equation on the right, then get Theorem 1 as follow.Theorem 1 , .Remark 1 The result of theorem 1 is a regression equation. 2.2 Crack terms to offset for summationWe calculate () (1) to get the solution of .We directly calculate the more general form .Crack terms to offset for summation is a important mathematical thinking method3, 4, now we use this solving the problem.Because ， so,()Apparently in () (1) the positive term will offset with the second negative term after it, The last remaining is and . But , so.We get Theorem 2 as follow.Theorem 2 ，.Now let ，through theorem 2 we get, ,push this result into ()(1) can get . This as same as the result of Undetermined coefficient to solve SPACC By the result of 2.1 and 2.3 its very easy to get a general rule as follow theorem.Theorem3 The exponent of the highest exponent of must be . Based on theorem3, we can directly start from the the results of problem to solve it by undetermined coefficient5, 6 .Set, ()Now give particular value,for example then push these particular value into (),we get the follow linear equations () of unknown variable ()Solve the sparse linear equations7-9() get the value of ,then put them into () we will get the value of .3 AcknowledgementThanks for the support of ShangLuo university education reform fund project 10jyjx01006 and 08sky028, and thanks the teachers and students of computer science department of ShangLuo university for helping us in the process of data acquisition and model testing.4 Summary Start from the easy to the difficult and complicated, some methods to solve SPACC rae discussed. From the special case of SPACC and promoted to its general situation. “2.1 Rise the exponent to spread and offset under dislocation” and “Crack terms to offset for summation” have the very strong technical, give their detailed calculations and reasoning process. “2.3 Undetermined coefficient to solve SPACC” is the most simple ideas, but compared to the other two methods need larger amount of calculation. In fact to solve a SPACC, we can combine the thought and skills of the three methods and use them neatly to efficiently solve more similar series summation problem. References1 Geng G H. Data structure-C language descriptionM. Beijing: higher education press, 2005:33. 2 Wang Z Q. Feeling the beauty of series summation J. Learn weekly (C), 2011, (3) : 187-189. 3 Chen K J, Lin Y, Teng S Y. A method using and exploration on crack termJ China Science and Technology Review, 2010，(21):213-214.4 Wang Y. The commonly used method about summation series J. Reading and Writing (Education and Teaching Research) , 2011, (4):95-97.5 Zhao Q F. An analytical solution of lD linear harmonic oscillator under the perturbation system by undetermined coefficient methodJ. College Physics , 2011, 30(5):55 -58.6 Hu J S. Finding out Special Solutions for Inhomogene-ous Euler Equations by Using of Indeterminate Coeffic -ientsJ. Journal of Sichuan Normal University (Natural Science), 2011,30(5):55-58.7 Luo Z G, Zhong Y, Wu F. Preprocessing Techniques for Solving Sparse Linear SystemsJ. Computer Engineer-ing and Science , 2010, 32(12):89-97.8 NANNELL