Prove $a^{n} - 1 = (a-1)(a^{n-1}+a^{n-2}+a^{n-3} + cdots + a + 1)$ for all $n ge 1$ using induction
$begingroup$
Problem 1.1.3 in Burton's Elementary Number Theory (6th ed.) is stated as follows:
Use the Second Principle of Finite Induction to establish that for all $n ge 1$,
begin{align} a^{n} - 1 = (a-1)(a^{n-1}+a^{n-2}+a^{n-3} + cdots + a + 1)
end{align}
[Hint: $a^{n+1} - 1 = (a+1)(a^{n}-1) - a(a^{n-1}-1)$.]
I already came across a much simpler proof in terms of requiring fewer algebraic manipulations but it didn't use the hint given in the problem statement. Right below is my attempt at proving the statement and I wish someone could confirm what I've done.
Proof by induction.
Base case. When $n =1$, LHS = $a^{1} - 1 = a-1$ and RHS = $(a-1)(a^{1-1}) = a-1$. Thus LHS = RHS.
Inductive step. Let's assume that $ a^{k} - 1 = (a-1)(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1) $ holds for $ 1, 2, ldots k $. Then
begin{align*}
a^{k+1} - 1 &= (a+1)(a^{k}-1) - a(a^{k-1}-1) \
&= (a+1)(a^{k}-1) - (a^{k}-a) \
&= (a+1)(a^{k}-1) - [(a^{k} -1) + (1 -a)] \
&= (a+1)(a^{k}-1) - (a^{k} -1) - (1 -a) \
&= [(a+1)(a^{k}-1) - (a^{k} -1)] + (a-1) \
&= (a^{k}-1)[a+1-1] + (a-1) \
&= (a^{k}-1)cdot a + (a-1) \
&= (a-1)(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1)cdot a + (a-1) \
&= (a-1)[(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1)cdot a + 1] \
&= (a-1)(a^{k}+a^{k-1}+a^{k-2} + cdots + a^{2} + a + 1) \
end{align*}
which is precisely the right side of the formula in the problem statement when $n = (k+1)$. Therefore by the principle of mathematical induction the formula holds for all $n ge 1$.
elementary-number-theory induction
asked Jan 16 at 19:32
uzlxxxxuzlxxxx
354
$endgroup$
add a comment |
$begingroup$
Problem 1.1.3 in Burton's Elementary Number Theory (6th ed.) is stated as follows:
Use the Second Principle of Finite Induction to establish that for all $n ge 1$,
begin{align} a^{n} - 1 = (a-1)(a^{n-1}+a^{n-2}+a^{n-3} + cdots + a + 1)
end{align}
[Hint: $a^{n+1} - 1 = (a+1)(a^{n}-1) - a(a^{n-1}-1)$.]
I already came across a much simpler proof in terms of requiring fewer algebraic manipulations but it didn't use the hint given in the problem statement. Right below is my attempt at proving the statement and I wish someone could confirm what I've done.
Proof by induction.
Base case. When $n =1$, LHS = $a^{1} - 1 = a-1$ and RHS = $(a-1)(a^{1-1}) = a-1$. Thus LHS = RHS.
Inductive step. Let's assume that $ a^{k} - 1 = (a-1)(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1) $ holds for $ 1, 2, ldots k $. Then
begin{align*}
a^{k+1} - 1 &= (a+1)(a^{k}-1) - a(a^{k-1}-1) \
&= (a+1)(a^{k}-1) - (a^{k}-a) \
&= (a+1)(a^{k}-1) - [(a^{k} -1) + (1 -a)] \
&= (a+1)(a^{k}-1) - (a^{k} -1) - (1 -a) \
&= [(a+1)(a^{k}-1) - (a^{k} -1)] + (a-1) \
&= (a^{k}-1)[a+1-1] + (a-1) \
&= (a^{k}-1)cdot a + (a-1) \
&= (a-1)(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1)cdot a + (a-1) \
&= (a-1)[(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1)cdot a + 1] \
&= (a-1)(a^{k}+a^{k-1}+a^{k-2} + cdots + a^{2} + a + 1) \
end{align*}
which is precisely the right side of the formula in the problem statement when $n = (k+1)$. Therefore by the principle of mathematical induction the formula holds for all $n ge 1$.
elementary-number-theory induction
asked Jan 16 at 19:32
uzlxxxxuzlxxxx
354
$endgroup$
$begingroup$
How is your proof not using the hint? In its first line?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:37
$begingroup$
@HagenvonEitzen What I meant is that I came across someone else's proof for the same problem but they didn't use the hint given in the problem. I've used the hint in my proof but I was doubtful the proof was correct so I wanted another person to confirm it.
$endgroup$
– uzlxxxx
Jan 16 at 23:22
add a comment |
$begingroup$
Problem 1.1.3 in Burton's Elementary Number Theory (6th ed.) is stated as follows:
Use the Second Principle of Finite Induction to establish that for all $n ge 1$,
begin{align} a^{n} - 1 = (a-1)(a^{n-1}+a^{n-2}+a^{n-3} + cdots + a + 1)
end{align}
[Hint: $a^{n+1} - 1 = (a+1)(a^{n}-1) - a(a^{n-1}-1)$.]
I already came across a much simpler proof in terms of requiring fewer algebraic manipulations but it didn't use the hint given in the problem statement. Right below is my attempt at proving the statement and I wish someone could confirm what I've done.
Proof by induction.
Base case. When $n =1$, LHS = $a^{1} - 1 = a-1$ and RHS = $(a-1)(a^{1-1}) = a-1$. Thus LHS = RHS.
Inductive step. Let's assume that $ a^{k} - 1 = (a-1)(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1) $ holds for $ 1, 2, ldots k $. Then
begin{align*}
a^{k+1} - 1 &= (a+1)(a^{k}-1) - a(a^{k-1}-1) \
&= (a+1)(a^{k}-1) - (a^{k}-a) \
&= (a+1)(a^{k}-1) - [(a^{k} -1) + (1 -a)] \
&= (a+1)(a^{k}-1) - (a^{k} -1) - (1 -a) \
&= [(a+1)(a^{k}-1) - (a^{k} -1)] + (a-1) \
&= (a^{k}-1)[a+1-1] + (a-1) \
&= (a^{k}-1)cdot a + (a-1) \
&= (a-1)(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1)cdot a + (a-1) \
&= (a-1)[(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1)cdot a + 1] \
&= (a-1)(a^{k}+a^{k-1}+a^{k-2} + cdots + a^{2} + a + 1) \
end{align*}
which is precisely the right side of the formula in the problem statement when $n = (k+1)$. Therefore by the principle of mathematical induction the formula holds for all $n ge 1$.
elementary-number-theory induction
asked Jan 16 at 19:32
uzlxxxxuzlxxxx
354
$endgroup$
Problem 1.1.3 in Burton's Elementary Number Theory (6th ed.) is stated as follows:
Use the Second Principle of Finite Induction to establish that for all $n ge 1$,
begin{align} a^{n} - 1 = (a-1)(a^{n-1}+a^{n-2}+a^{n-3} + cdots + a + 1)
end{align}
[Hint: $a^{n+1} - 1 = (a+1)(a^{n}-1) - a(a^{n-1}-1)$.]
I already came across a much simpler proof in terms of requiring fewer algebraic manipulations but it didn't use the hint given in the problem statement. Right below is my attempt at proving the statement and I wish someone could confirm what I've done.
Proof by induction.
Base case. When $n =1$, LHS = $a^{1} - 1 = a-1$ and RHS = $(a-1)(a^{1-1}) = a-1$. Thus LHS = RHS.
Inductive step. Let's assume that $ a^{k} - 1 = (a-1)(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1) $ holds for $ 1, 2, ldots k $. Then
begin{align*}
a^{k+1} - 1 &= (a+1)(a^{k}-1) - a(a^{k-1}-1) \
&= (a+1)(a^{k}-1) - (a^{k}-a) \
&= (a+1)(a^{k}-1) - [(a^{k} -1) + (1 -a)] \
&= (a+1)(a^{k}-1) - (a^{k} -1) - (1 -a) \
&= [(a+1)(a^{k}-1) - (a^{k} -1)] + (a-1) \
&= (a^{k}-1)[a+1-1] + (a-1) \
&= (a^{k}-1)cdot a + (a-1) \
&= (a-1)(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1)cdot a + (a-1) \
&= (a-1)[(a^{k-1}+a^{k-2}+a^{k-3} + cdots + a + 1)cdot a + 1] \
&= (a-1)(a^{k}+a^{k-1}+a^{k-2} + cdots + a^{2} + a + 1) \
end{align*}
which is precisely the right side of the formula in the problem statement when $n = (k+1)$. Therefore by the principle of mathematical induction the formula holds for all $n ge 1$.
elementary-number-theory induction
elementary-number-theory induction
asked Jan 16 at 19:32
uzlxxxxuzlxxxx
354
asked Jan 16 at 19:32
uzlxxxxuzlxxxx
354
edited Jan 16 at 23:14
uzlxxxx
asked Jan 16 at 19:32
uzlxxxxuzlxxxx
354
asked Jan 16 at 19:32
uzlxxxxuzlxxxx
354
asked Jan 16 at 19:32
uzlxxxxuzlxxxx
354
354
$begingroup$
How is your proof not using the hint? In its first line?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:37
$begingroup$
@HagenvonEitzen What I meant is that I came across someone else's proof for the same problem but they didn't use the hint given in the problem. I've used the hint in my proof but I was doubtful the proof was correct so I wanted another person to confirm it.
$endgroup$
– uzlxxxx
Jan 16 at 23:22
add a comment |
$begingroup$
How is your proof not using the hint? In its first line?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:37
$begingroup$
@HagenvonEitzen What I meant is that I came across someone else's proof for the same problem but they didn't use the hint given in the problem. I've used the hint in my proof but I was doubtful the proof was correct so I wanted another person to confirm it.
$endgroup$
– uzlxxxx
Jan 16 at 23:22
$begingroup$
How is your proof not using the hint? In its first line?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:37
$begingroup$
How is your proof not using the hint? In its first line?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:37
$begingroup$
@HagenvonEitzen What I meant is that I came across someone else's proof for the same problem but they didn't use the hint given in the problem. I've used the hint in my proof but I was doubtful the proof was correct so I wanted another person to confirm it.
$endgroup$
– uzlxxxx
Jan 16 at 23:22
$begingroup$
@HagenvonEitzen What I meant is that I came across someone else's proof for the same problem but they didn't use the hint given in the problem. I've used the hint in my proof but I was doubtful the proof was correct so I wanted another person to confirm it.
$endgroup$
– uzlxxxx
Jan 16 at 23:22
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The only problem with your proof is that you failed to check and confirm that for the base case, when $n=1$, the given proposition holds. Add that to your proof, and you're good to go.
It may seem utterly obvious and not worth mentioning in a proof, but without proving the base case $n=1$, your proof is meaningless in terms of providing an inductive proof.
Note also that you are indeed using the hint when you write for first line in determining $a^{k+1}$.
answered Jan 16 at 19:38
jordan_glenjordan_glen
1
$endgroup$
$begingroup$
Great! I was so invested in the induction step that I totally forgot about checking the base case.
$endgroup$
– uzlxxxx
Jan 16 at 23:17
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3076189%2fprove-an-1-a-1an-1an-2an-3-cdots-a-1-for-all-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The only problem with your proof is that you failed to check and confirm that for the base case, when $n=1$, the given proposition holds. Add that to your proof, and you're good to go.
It may seem utterly obvious and not worth mentioning in a proof, but without proving the base case $n=1$, your proof is meaningless in terms of providing an inductive proof.
Note also that you are indeed using the hint when you write for first line in determining $a^{k+1}$.
answered Jan 16 at 19:38
jordan_glenjordan_glen
1
$endgroup$
$begingroup$
Great! I was so invested in the induction step that I totally forgot about checking the base case.
$endgroup$
– uzlxxxx
Jan 16 at 23:17
add a comment |
$begingroup$
The only problem with your proof is that you failed to check and confirm that for the base case, when $n=1$, the given proposition holds. Add that to your proof, and you're good to go.
It may seem utterly obvious and not worth mentioning in a proof, but without proving the base case $n=1$, your proof is meaningless in terms of providing an inductive proof.
Note also that you are indeed using the hint when you write for first line in determining $a^{k+1}$.
answered Jan 16 at 19:38
jordan_glenjordan_glen
1
$endgroup$
$begingroup$
Great! I was so invested in the induction step that I totally forgot about checking the base case.
$endgroup$
– uzlxxxx
Jan 16 at 23:17
add a comment |
$begingroup$
The only problem with your proof is that you failed to check and confirm that for the base case, when $n=1$, the given proposition holds. Add that to your proof, and you're good to go.
It may seem utterly obvious and not worth mentioning in a proof, but without proving the base case $n=1$, your proof is meaningless in terms of providing an inductive proof.
Note also that you are indeed using the hint when you write for first line in determining $a^{k+1}$.
answered Jan 16 at 19:38
jordan_glenjordan_glen
1
$endgroup$
The only problem with your proof is that you failed to check and confirm that for the base case, when $n=1$, the given proposition holds. Add that to your proof, and you're good to go.
It may seem utterly obvious and not worth mentioning in a proof, but without proving the base case $n=1$, your proof is meaningless in terms of providing an inductive proof.
Note also that you are indeed using the hint when you write for first line in determining $a^{k+1}$.
answered Jan 16 at 19:38
jordan_glenjordan_glen
1
edited Jan 16 at 21:13
answered Jan 16 at 19:38
jordan_glenjordan_glen
1
answered Jan 16 at 19:38
jordan_glenjordan_glen
1
answered Jan 16 at 19:38
jordan_glenjordan_glen
1
1
$begingroup$
Great! I was so invested in the induction step that I totally forgot about checking the base case.
$endgroup$
– uzlxxxx
Jan 16 at 23:17
add a comment |
$begingroup$
Great! I was so invested in the induction step that I totally forgot about checking the base case.
$endgroup$
– uzlxxxx
Jan 16 at 23:17
$begingroup$
Great! I was so invested in the induction step that I totally forgot about checking the base case.
$endgroup$
– uzlxxxx
Jan 16 at 23:17
$begingroup$
Great! I was so invested in the induction step that I totally forgot about checking the base case.
$endgroup$
– uzlxxxx
Jan 16 at 23:17
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3076189%2fprove-an-1-a-1an-1an-2an-3-cdots-a-1-for-all-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
How is your proof not using the hint? In its first line?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:37
$begingroup$
@HagenvonEitzen What I meant is that I came across someone else's proof for the same problem but they didn't use the hint given in the problem. I've used the hint in my proof but I was doubtful the proof was correct so I wanted another person to confirm it.
$endgroup$
– uzlxxxx
Jan 16 at 23:22