Mathematical Induction

A page of uncommon problems, most closely connected with number theory. Some properties may be proved in different ways. A direct inductive proof is given in the majority of the cases. For more exercises, problems, puzzles, games, math riddles, brain teasers, etc. to see Math Links (not only of math induction).

For those interested in math contests and competitions to see the site:
Art of Problem Solving

New Problems

Additional problems in PDF format.

Let F(n) be the n^th Fibonacci number, let p be a prime number distinct from 2 and 5, and let k(p) denote the period of the Fibonacci sequence modulo p (Pisano period). Prove that for any non-negative integer n:
p³ divides ((p²-1)F(k(p)n)/k(p))-nF(p²-1)

The following Pari/GP code is part of a new problem still in revision.

d=2

suc(n)=if(n==0,3,if(n==1,0,if(n==2,2*a,a*suc(n-2)+(a-1)*suc(n-3))))

{for(n=0,n=5,print(factor(sum(i=0,d,binomial(d,i)*(-1)^(d-i)*(suc(6*(i+n)+4))))))}

{for(n=0,n=5,print(factor(sum(i=0,d,binomial(d,i)*(suc(6)-2)^i*(-(a-1)^6)^(d-i)*( 
if(6*(n+i-d)+4<0,(suc(-(6*(n+i-d)+4))-1)/(a-1)^(-(6*(n+i-d)+4)),suc(6*(n+i-d)+4)-1) 
)))))}

Comments, references and external links

A problem proposed by me in The Prime Puzzles and Problems Connection, can be found here.
The identity x⁴+y⁴+(x+y)⁴=2(x²+xy+y²)², which is related to Problem 5, is known as "Proth's identity". A slight variant of this result is "Candido's identity". See the following extract from the article: Equal Sums of Three Fourth Powers or What Ramanujan Could Have Said. Note that the reference would indicate Volumen 2 instead of 3. The book History of the Theory of Numbers (Volume 2) by Leonard E. Dickson can be found here.
Link of interest: Sums of Powers in Terms of Symmetric Functions.
Several problems are now included in the Handbook of Mathematical Induction: Theory and Applications.
Sequence A002715 in OEIS is related to the c_n's mentioned in Problem 2 (newproblems.pdf file). The closed formula is:
A002715(2n)=(L(2ⁿ⁺²)-1)/2 and A002715(2n+1)=L(2ⁿ⁺²), where L(n) is the n^th Lucas number. This can be proved using a variant of induction. We have to prove that the property is true for n=0, and then prove something of the form P(2k)=>P(2k+1) and P(2k-1)=>P(2k). See also sequence A001510, whose closed form can be found in the Fibonacci Quarterly article given as a reference. Note that the relation mentioned between both sequences is correct.

Interactive Induction

See PHP Script for Problem 21.

Contact

Email Form