Prove that for every integer n >1 (greater than or equal to 1), {[(n+1)^n]-1}/(n

Question

Prove that for every integer n >1 (greater than or equal to 1), {[(n+1)^n]-1}/(n^2)

aka n^2 divides [(n+1)^n]-1 Is there a way to solve this by induction, setting it up: 1+2+7+...+n = {[(n+1)^n]-1}/(n^2) ??? Prove that for every integer n >1 (greater than or equal to 1), {[(n+1)^n]-1}/(n^2) aka n^2 divides [(n+1)^n]-1 Is there a way to solve this by induction, setting it up: 1+2+7+...+n = {[(n+1)^n]-1}/(n^2) ???

Explanation / Answer

Now I get it. OK. (n+1)^n is the binomial expression (a+b)^n so it is: (a+b)^n = F(n,0).a^n.b^0 + F(n,1).a^(n-1).b^1 + F(n,2).a^(n-2).b2 ...etc… until … + F(n,n).a^0.b^n Where F(n,i) is the binomial coefficient for (n,i) usually written (n on top of i). If you are not familiar with that ===> See wikipedia "Binomial Theorem" and Pascal's triangle (one of the neatest things in Math). It means (a+b)^n is the sum, for i= n of all the terms like: F(n,i).a^(n-i).b^i Examples: (a+b)^2 = a^2 + 2a^1b^1 + b^2 (a+b)^3 = a^3 + 3.a^2.b^1 + 3a.^1b^2 + b^3 (note how all powers in each term add up to 3) (a+b)^4 = a^4 + 4.a^3.b + 6.a^2.b^2 + 4a.b^3 + b^4 (now powers in each term add up to 4) In our case a=n and b=1 simplifies the formula as: (1+n)^n = Sum for i=0 to n of all the [F(n,i).n^(n-i) ] ..... As b=1, now (b^i) is always 1. Now, for any of these terms, if (n-i) is 2 or more, that implies it is a multiple of n^2. So we only have to worry about the last two terms of the sum which are [n-(n-1)] = 1 and [n-n] = 0 These two terms are: F(n,n-1) n^1 and F(n,n) n^0 And if you check out the value of F(n,i) you will see (Wikipedia or your book): F(n,n) = 1 F(n,n-1) = n So the last two terms are: F(n,n-1) n^1 = n.n = n^2 And F(n,n) n^0 = 1.1 = 1 And remember we said: For all i from 0 to n-2 we have (n-i) >= 2 and therefore: F(n,i) n^(n-i) = F(n,i) n^2 . n^(n-i-2) So we can write the whole sum as: (n+1)^n = Sum { for [i=0 to (n-2)] of the F(n,i) n^2 n^(n-i-2)} + F(n,n-1) n^1 + F(n,n) n^0 And that is: (n+1)^n = Sum { for [i=0 to (n-2)] of the F(n,i) n^2 n^(n-i-2)} + n^2 + 1 Or, factoring n^2 for all terms except the last one (1): (n+1)^n = (n^2) [ Sum { for [i=0 to (n-2)] of the F(n,i) n^(n-i-2)} + 1] + 1 Therefore: [ (n+1)^n – 1 ] = (n^2) [ Sum { for [i=0 to (n-2)] of the F(n,i) n^(n-i-2)} + 1] And that is clearly divisible by n^2 …

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.