help with induction: (a+1)^n -a·n-1 can be divided by a^2

[shangkarao]

help with induction: (a+1)^n -a·n-1 can be divided by a^2

hello friends,
i have this assignment in induction i can not solve, if someone could give me a hand i will be very grateful.

prove that-

∀n∈ℕ and ∀a∈ℕ, the number (a+1)ⁿ -a·n-1
can be divided by a² with no remainder.


thank you so much guys!

 

[tkhunny]

hello friends,
i have this assignment in induction i can not solve, if someone could give me a hand i will be very grateful.

prove that-∀n∈ℕ and ∀a∈ℕ, the number (a+1)ⁿ -a·n-1
can be divided by a² with no remainder.


thank you so much guys!

Have you considered the expansion of the first term?

 

[Dr.Peterson]

hello friends,
i have this assignment in induction i can not solve, if someone could give me a hand i will be very grateful.

prove that-

∀n∈ℕ and ∀a∈ℕ, the number (a+1)ⁿ -a·n-1
can be divided by a² with no remainder.


thank you so much guys!

It sounds like you know how to do induction, but got stuck along the way. Can you show us how you started, so we can see where you need help? What is the induction hypothesis? What is it that you then have to show?

 

[shangkarao]

i tried to solve for n=a=1, and i assumed that a and n is true for the expression,
then, i tried to solve for a= a+1, and n= n+1, and i tried to change the expression so i can get the base form of the expression, so i can apply reduction.

 

[shangkarao]

(a+1+1)ⁿ⁺¹ -(n+1)(a+1)-1
—————————————— =
(a+1)²


(a+2)·(a+2)ⁿ -(an+n+a+1)-1
—————————————— =
(a+1)²



(a+2)·(a+2)ⁿ -an-n-a-2
—————————————— =
(a+1)²



(a+2)·(a+2)ⁿ -n(a+1)-(a+2)
—————————————— =
(a+1)²



(a+2)·(a+2)ⁿ -n(a+1)-(a+2)
—————————————— =
(a+1)²





(a+2) [ (a+2)ⁿ-1]-n(a+1)
—————————————— =
(a+1)²



this is what i have so far.

 

[Dr.Peterson]

i tried to solve for n=a=1, and i assumed that a and n is true for the expression,
then, i tried to solve for a= a+1, and n= n+1, and i tried to change the expression so i can get the base form of the expression, so i can apply reduction.

The word "solve" is not appropriate here. I think you mean that you first assumed that n and a are 1 as the base case; then you assumed that the claim is true for a given n and a, and tried to show that it is true when a is replaced by a+1 and n by n+1.

You can't really use induction simultaneously on two variables. So I think that is your first difficulty.

I would use induction only on n, and take "for all a" as part of the statement.

So the base case is that (taking n=1 but leaving a as a variable),

(a+1)ⁿ - an - 1 = (a+1)¹ - a*1 - 1 = a + 1 - a - 1 = 0 is divisible by a² for all a.
​

Since 0 is divisible by all natural numbers, the base case is true.

Now, the induction hypothesis (assumed to be true for a given value of n) is

(a+1)ⁿ - an - 1 is divisible by a² for all natural numbers a.
​

You have to show that, on that assumption,

(a+1)ⁿ⁺¹ - a(n+1) - 1 is divisible by a² for all natural numbers a.
​

By changing only n, I have made the work much easier than the work you showed. Give that a try.

 

[shangkarao]

thank you for your replay,

i tried this so far, and then got stuck at the end.


(a+1)ⁿ⁺¹ -a(n+1)-1
——————————— =
a²


(a+1) (a+1)ⁿ -an-a-1
—————————————— =
a²


(a+1) (a+1)ⁿ -an-(a+1)
—————————————— =
a²


(a+1) [ (a+1)ⁿ -1 ] -an
———————————— =
a²

 

[HallsofIvy]

I wouldn't use induction (at least not directly). \(\displaystyle (a+ 1)^n= \sum_{i= 0}^n \begin{pmatrix}n \\ i\end{pmatrix} a^i\). Subtracting "na+ 1" starts the sum at \(\displaystyle a^2\) leaving \(\displaystyle (a+ 1)^n= \sum_{i= 2}^n \begin{pmatrix}n \\ i\end{pmatrix} a^i= a^2\left(\sum_{i= 2}^{n} \begin{pmatrix}n \\ i\end{pmatrix} a^{i-2}\right)\).

 

[shangkarao]

I wouldn't use induction (at least not directly). \(\displaystyle (a+ 1)^n= \sum_{i= 0}^n \begin{pmatrix}n \\ i\end{pmatrix} a^i\). Subtracting "na+ 1" starts the sum at \(\displaystyle a^2\) leaving \(\displaystyle (a+ 1)^n= \sum_{i= 2}^n \begin{pmatrix}n \\ i\end{pmatrix} a^i= a^2\left(\sum_{i= 2}^{n} \begin{pmatrix}n \\ i\end{pmatrix} a^{i-2}\right)\).

thank you, but i need a different proof.
i also didn't fully understand what you did.

 

[Dr.Peterson]

thank you, but i need a different proof.
i also didn't fully understand what you did.

If you are learning induction, you don't need to understand what he did (unless you choose to).

 

[Dr.Peterson]

thank you for your replay,

i tried this so far, and then got stuck at the end.


(a+1)ⁿ⁺¹ -a(n+1)-1
——————————— =
a²


(a+1) (a+1)ⁿ -an-a-1
—————————————— =
a²


(a+1) (a+1)ⁿ -an-(a+1)
—————————————— =
a²


(a+1) [ (a+1)ⁿ -1 ] -an
———————————— =
a²

You're showing a denominator here only to indicate that you want to show this division will yield an integer, right? It isn't necessary to do that; you can just work with your numerator and show that it is equal to a²(...).

Use the induction hypothesis: (a+1)ⁿ - an - 1 is divisible by a². One way to express this is that (a+1)ⁿ - an - 1 = ka² for some integer k. So (a+1)ⁿ - 1 = ka² + an. Put that into your expression, and see if you can factor a² out of it, showing that the numerator is divisible by a².

 

[JeffM]

When using induction to prove that the proposition is true for k + 1, you use the fact that the proposition is true for k (and perhaps also the fact that it is true for 1). That means that you must decompose whatever it is that you are talking about in terms of k (or k and 1).

\(\displaystyle \displaystyle \text {PROVE: } a,\ n \in \mathbb Z^+ \implies \exists \ b_n \text { such that } b_n \in \mathbb Z_{\ge 0} \text { and } a^2b_n = (a + 1)^n - an - 1.\)

\(\displaystyle n = 1 \implies \displaystyle (a + 1)^n - an - 1 = (a + 1)^1 - a(1) - 1 = a = a + 1 - a - 1 = 0 = a^2 * 0.\)

\(\displaystyle \text {Let } b_1 = 0 \implies b_0 \in \mathbb Z_{\ge 0} \text { and } (a + 1)^1 - an - 1 = a^2b_1.\)

\(\displaystyle \therefore (a + 1)^n - an - 1 = a^2b_n \text { and } b_n \in \mathbb Z_{\ge 0} \text { if } n = 1.\)

\(\displaystyle \therefore \exists \text { non-empty set } \mathbb K \text { such that, for an arbitrary member } k \text { of } \mathbb K,\\

k \in \mathbb Z^+ \text { and } \exists \ b_k \text { such that } b_k \in \mathbb Z_{\ge 0} \text { and } (a + 1)^k - ak - 1 = a^2b_k.\)

\(\displaystyle \therefore (a + 1)^k = a^2b_n + ak + 1.\)

So far this has been very routine. Now use tkhunny's idea.

\(\displaystyle (a + 1)^{(k+1)} - a(k + 1) - 1 = (a + 1)(a + 1)^k - ak - a - 1 =\\

a(a + 1)^k + (a + 1)^k - ak - 1 - a = a(a^2b_k + ak + 1) + a^2b_k + ak + 1 - ak - 1 - a =\\

a^3b_k + a^2k + a + a^2b_k - a = a^2(ab_k + b_k + k).\)

\(\displaystyle \text {Let } b_{(k+1)} = ab_k + b_k + k \implies (a + 1)^{(k+1)} - a(k + 1) - 1 = a^2b_{(k+1)}.\)

However, the proof is not yet complete. What more must be done? Can you do it?

 

[lookagain]

It has been fours days since the problem has been posted. I will post a remaining part of the solution that fits with the OP's
requirement.

I see that JeffM's and HallsofIvy's posts are relatively notation-heavy, and the OP doesn't tell us which parts are not understandable.
Make it simpler/user-friendly to read and follow.

I will leave off where Dr. Peterson started after the base step. Dr. Peterson, I'm using "k" in the "n = k" portion, so I will not use
\(\displaystyle \ "ka^2" \ \) for a multiple of \(\displaystyle "a^2."\)


Assume the statement is true for n = k:

\(\displaystyle (a + 1)^k \ - \ ak \ - \ 1 \ = \ ra^2, \ \ \ \) for r, a positive integer.


Show it is true for n = k + 1:

\(\displaystyle (a + 1)^{k + 1} \ - \ a(k + 1) \ - \ 1 \ = \ \) some multiple of \(\displaystyle \ a^2\).


Begin:
-------

\(\displaystyle (a + 1)^k \ - \ ak \ - \ 1 \ = \ ra^2 \ \ \) for r, a positive integer.

\(\displaystyle (a + 1)[(a + 1)^k \ - \ 1(ak \ + \ 1)] \ = \ (a + 1)[ra^2] \)

\(\displaystyle (a + 1)^{k + 1} \ - \ (a + 1)(ak \ + \ 1) \ = \ r(a + 1)a^2 \)

\(\displaystyle (a + 1)^{k + 1} \ - \ a^2k \ - \ a \ - \ ak \ - \ 1 \ = \ r(a + 1)a^2 \)

\(\displaystyle (a + 1)^{k + 1} \ - \ ak \ - \ a \ - \ 1 \ - \ a^2k \ = \ r(a + 1)a^2 \)

\(\displaystyle (a + 1)^{k + 1} \ - \ a(k + 1) \ - \ 1 \ = \ a^2k \ + \ r(a + 1)a^2 \)

\(\displaystyle (a + 1)^{k + 1} \ - \ a(k + 1) \ - \ 1 \ = \ [k \ + \ r(a + 1)]a^2 \)


The right-hand side is a multiple of \(\displaystyle \ a^2\).


Thus, by the Principle of Mathematical Induction, the original statement is true.