Dtjytyk

Confusion with the nameplate of an induction motor

What has been your most complicated TikZ drawing?

When were linguistics departments first established

Latest web browser compatible with Windows 98

Replacing Windows 7 security updates with anti-virus?

Decoding assembly instructions in a Game Boy disassembler

Straight line with arrows and dots

Word for a person who has no opinion about whether god exists

What to do when during a meeting client people start to fight (even physically) with each others?

Time dilation for a moving electronic clock

"However" used in a conditional clause?

If the Captain's screens are out, does he switch seats with the co-pilot?

Is it true that real estate prices mainly go up?

What is the difference between "shut" and "close"?

Welcoming 2019 Pi day: How to draw the letter π?

How does Dispel Magic work against Stoneskin?

Good allowance savings plan?

What does it mean when multiple 々 marks follow a 、?

What is the definition of "Natural Selection"?

Why would a jet engine that runs at temps excess of 2000°C burn when it crashes?

validation vs test vs training accuracy, which one to compare for claiming overfit?

Humans have energy, but not water. What happens?

Is going from continuous data to categorical always wrong?

Is it illegal in Germany to take sick leave if you caused your own illness with food?

Fibonacci Number basis Induction

Proof by Induction: Alternating Sum of Fibonacci NumbersProof by induction on Fibonacci numbers: show that $f_nmid f_{2n}$Prove that for each Fibonacci number $f_{4n}$ is a multiple of $3$.Prove by induction fibonacci variationFibonacci induction proof?A conjecture about Fibonacci numbersProof by induction FibonacciProve that sum of the square of Fibonacci numbers from 1 to n is equal to the nth Fibonacci number multiplied by the n+1 th Fibonacci NumberConsecutive Fibonacci NumbersShowing that the $n$-th Fibonacci number $f_n$ satisfies $f_n < 2^n$

2

$begingroup$

The Fibonacci numbers are defined as follows:
$$F_1 = 0, quad
F_2 = 1, quad
F_n = F_{n−2} + F_{n−1}, text{ for all } n geq 3$$
Prove the following using induction:

Zeckendorf's theorem. One can express any positive integer as a sum of distinct
Fibonacci numbers, no two of which have consecutive Fibonacci indices. For example,
$79 = 55 + 21 + 3$.

We will prove this claim by using induction on $n$.

IH: Assume that the claim is true when $n = k$, for some $k > 3$.

$F_k = F_{k−2} + F_{k−1}$

BC: k = 3

Am I on the right track for this? Not sure where to go from here

induction fibonacci-numbers

share|cite|improve this question

edited Mar 10 at 2:41

darij grinberg

11.2k33167

asked Nov 2 '14 at 15:41

user3434743user3434743

1338

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  First, you should not reuse $n$ from the definition of the Fibonacci numbers. You need to prove it for $1$, (otherwise it might not be true for all positive integers), so that might as well be your base case: Just say $1=F_2$ You need to distinguish between the number you are expressing and the index of the Fibonacci numbers, $k$ appears both ways.
  $endgroup$
  – Ross Millikan
  Nov 2 '14 at 15:54
  

  
  
  
  

add a comment | 

2

$begingroup$

The Fibonacci numbers are defined as follows:
$$F_1 = 0, quad
F_2 = 1, quad
F_n = F_{n−2} + F_{n−1}, text{ for all } n geq 3$$
Prove the following using induction:

Zeckendorf's theorem. One can express any positive integer as a sum of distinct
Fibonacci numbers, no two of which have consecutive Fibonacci indices. For example,
$79 = 55 + 21 + 3$.

We will prove this claim by using induction on $n$.

IH: Assume that the claim is true when $n = k$, for some $k > 3$.

$F_k = F_{k−2} + F_{k−1}$

BC: k = 3

Am I on the right track for this? Not sure where to go from here

induction fibonacci-numbers

share|cite|improve this question

edited Mar 10 at 2:41

darij grinberg

11.2k33167

asked Nov 2 '14 at 15:41

user3434743user3434743

1338

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  First, you should not reuse $n$ from the definition of the Fibonacci numbers. You need to prove it for $1$, (otherwise it might not be true for all positive integers), so that might as well be your base case: Just say $1=F_2$ You need to distinguish between the number you are expressing and the index of the Fibonacci numbers, $k$ appears both ways.
  $endgroup$
  – Ross Millikan
  Nov 2 '14 at 15:54
  

  
  
  
  

add a comment | 

$begingroup$

The Fibonacci numbers are defined as follows:
$$F_1 = 0, quad
F_2 = 1, quad
F_n = F_{n−2} + F_{n−1}, text{ for all } n geq 3$$
Prove the following using induction:

Zeckendorf's theorem. One can express any positive integer as a sum of distinct
Fibonacci numbers, no two of which have consecutive Fibonacci indices. For example,
$79 = 55 + 21 + 3$.

We will prove this claim by using induction on $n$.

IH: Assume that the claim is true when $n = k$, for some $k > 3$.

$F_k = F_{k−2} + F_{k−1}$

BC: k = 3

Am I on the right track for this? Not sure where to go from here

induction fibonacci-numbers

share|cite|improve this question

edited Mar 10 at 2:41

darij grinberg

11.2k33167

asked Nov 2 '14 at 15:41

user3434743user3434743

1338

$endgroup$

share|cite|improve this question

edited Mar 10 at 2:41

darij grinberg

11.2k33167

asked Nov 2 '14 at 15:41

user3434743user3434743

1338

share|cite|improve this question

edited Mar 10 at 2:41

darij grinberg

11.2k33167

asked Nov 2 '14 at 15:41

user3434743user3434743

1338

edited Mar 10 at 2:41

darij grinberg

11.2k33167

edited Mar 10 at 2:41

darij grinberg

11.2k33167

asked Nov 2 '14 at 15:41

user3434743user3434743

1338

asked Nov 2 '14 at 15:41

user3434743user3434743

1338

2 Answers
2

active

oldest

votes

1

$begingroup$

It is perhaps better to suppose that the claim is true for $nle k$ for some $kge$, say $3$, (it is easy to check for $k=1, 2, 3$).

Let us consider $n=k+1$.

If $n=F_j$ for some $j$, then the claim is true.

Otherwise, let us suppose $F_j<n<F_{j+1}$. Let $n'=n-F_j$. Then $n'<F_{j+1}-F_j=F_{j-1}$.

By assumption, we can express $n'=sum_{iin I} F_i$. It is clear that $i<j-1$.

It is your job to verify that $n=n'+F_j=sum_{iin I} F_i+F_j$ is the desire expression.

Therefore the claim holds for $n$.

share|cite|improve this answer

answered Nov 2 '14 at 15:53

Ma MingMa Ming

6,5661331

$endgroup$

add a comment | 

0

$begingroup$

Suppose by induction any number between $1$ and $f_n$ can be written as a sum of distinct fibonacci numbers, we shall prove any number between $1$ and $f_{n+1}$ can be written as distinct fibonacci numbers. We must only prove it for numbers between $f_n$ and $f_{n+1}$

Pick such a number $a$ between $f_n$ and $f_{n+1}$, it can be written as $f_n+k$ where $k$ is a number between $1$ and $f_{n-1}$ by the definition of fibonacci. Since $k$ is under $f_n$ we can write $k$ as a sum of distinct fibonacci numbers not including $f_n$. so when we add the fibonaccis in $k$ with $f_n$ we get the desired way to write $a$.

share|cite|improve this answer

answered Nov 2 '14 at 15:50

Jorge Fernández HidalgoJorge Fernández Hidalgo

76.8k1294195

$endgroup$

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
});


}
});

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1002685%2ffibonacci-number-basis-induction%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

It is perhaps better to suppose that the claim is true for $nle k$ for some $kge$, say $3$, (it is easy to check for $k=1, 2, 3$).

Let us consider $n=k+1$.

If $n=F_j$ for some $j$, then the claim is true.

Otherwise, let us suppose $F_j<n<F_{j+1}$. Let $n'=n-F_j$. Then $n'<F_{j+1}-F_j=F_{j-1}$.

By assumption, we can express $n'=sum_{iin I} F_i$. It is clear that $i<j-1$.

It is your job to verify that $n=n'+F_j=sum_{iin I} F_i+F_j$ is the desire expression.

Therefore the claim holds for $n$.

share|cite|improve this answer

answered Nov 2 '14 at 15:53

Ma MingMa Ming

6,5661331

$endgroup$

add a comment | 

1

$begingroup$

It is perhaps better to suppose that the claim is true for $nle k$ for some $kge$, say $3$, (it is easy to check for $k=1, 2, 3$).

Let us consider $n=k+1$.

If $n=F_j$ for some $j$, then the claim is true.

Otherwise, let us suppose $F_j<n<F_{j+1}$. Let $n'=n-F_j$. Then $n'<F_{j+1}-F_j=F_{j-1}$.

By assumption, we can express $n'=sum_{iin I} F_i$. It is clear that $i<j-1$.

It is your job to verify that $n=n'+F_j=sum_{iin I} F_i+F_j$ is the desire expression.

Therefore the claim holds for $n$.

share|cite|improve this answer

answered Nov 2 '14 at 15:53

Ma MingMa Ming

6,5661331

$endgroup$

add a comment | 

$begingroup$

It is perhaps better to suppose that the claim is true for $nle k$ for some $kge$, say $3$, (it is easy to check for $k=1, 2, 3$).

Let us consider $n=k+1$.

If $n=F_j$ for some $j$, then the claim is true.

Otherwise, let us suppose $F_j<n<F_{j+1}$. Let $n'=n-F_j$. Then $n'<F_{j+1}-F_j=F_{j-1}$.

By assumption, we can express $n'=sum_{iin I} F_i$. It is clear that $i<j-1$.

It is your job to verify that $n=n'+F_j=sum_{iin I} F_i+F_j$ is the desire expression.

Therefore the claim holds for $n$.

share|cite|improve this answer

answered Nov 2 '14 at 15:53

Ma MingMa Ming

6,5661331

$endgroup$

share|cite|improve this answer

answered Nov 2 '14 at 15:53

Ma MingMa Ming

6,5661331

answered Nov 2 '14 at 15:53

Ma MingMa Ming

6,5661331

answered Nov 2 '14 at 15:53

Ma MingMa Ming

6,5661331

0

$begingroup$

Suppose by induction any number between $1$ and $f_n$ can be written as a sum of distinct fibonacci numbers, we shall prove any number between $1$ and $f_{n+1}$ can be written as distinct fibonacci numbers. We must only prove it for numbers between $f_n$ and $f_{n+1}$

Pick such a number $a$ between $f_n$ and $f_{n+1}$, it can be written as $f_n+k$ where $k$ is a number between $1$ and $f_{n-1}$ by the definition of fibonacci. Since $k$ is under $f_n$ we can write $k$ as a sum of distinct fibonacci numbers not including $f_n$. so when we add the fibonaccis in $k$ with $f_n$ we get the desired way to write $a$.

share|cite|improve this answer

answered Nov 2 '14 at 15:50

Jorge Fernández HidalgoJorge Fernández Hidalgo

76.8k1294195

$endgroup$

add a comment | 

0

$begingroup$

Suppose by induction any number between $1$ and $f_n$ can be written as a sum of distinct fibonacci numbers, we shall prove any number between $1$ and $f_{n+1}$ can be written as distinct fibonacci numbers. We must only prove it for numbers between $f_n$ and $f_{n+1}$

Pick such a number $a$ between $f_n$ and $f_{n+1}$, it can be written as $f_n+k$ where $k$ is a number between $1$ and $f_{n-1}$ by the definition of fibonacci. Since $k$ is under $f_n$ we can write $k$ as a sum of distinct fibonacci numbers not including $f_n$. so when we add the fibonaccis in $k$ with $f_n$ we get the desired way to write $a$.

share|cite|improve this answer

answered Nov 2 '14 at 15:50

Jorge Fernández HidalgoJorge Fernández Hidalgo

76.8k1294195

$endgroup$

add a comment | 

$begingroup$

Suppose by induction any number between $1$ and $f_n$ can be written as a sum of distinct fibonacci numbers, we shall prove any number between $1$ and $f_{n+1}$ can be written as distinct fibonacci numbers. We must only prove it for numbers between $f_n$ and $f_{n+1}$

Pick such a number $a$ between $f_n$ and $f_{n+1}$, it can be written as $f_n+k$ where $k$ is a number between $1$ and $f_{n-1}$ by the definition of fibonacci. Since $k$ is under $f_n$ we can write $k$ as a sum of distinct fibonacci numbers not including $f_n$. so when we add the fibonaccis in $k$ with $f_n$ we get the desired way to write $a$.

share|cite|improve this answer

answered Nov 2 '14 at 15:50

Jorge Fernández HidalgoJorge Fernández Hidalgo

76.8k1294195

$endgroup$

share|cite|improve this answer

answered Nov 2 '14 at 15:50

Jorge Fernández HidalgoJorge Fernández Hidalgo

76.8k1294195

answered Nov 2 '14 at 15:50

Jorge Fernández HidalgoJorge Fernández Hidalgo

76.8k1294195

answered Nov 2 '14 at 15:50

Jorge Fernández HidalgoJorge Fernández Hidalgo

76.8k1294195