Proof by Induction Homework: Proving F_n|F_{kn}

In summary, "Proof by induction" is a useful method in mathematics used to prove statements about natural numbers or other well-ordered sets. It involves using a base case and an inductive step to show that a statement holds for all values of a given variable. The statement "F_n|F_{kn}" means that the nth Fibonacci number divides the k*nth Fibonacci number. To prove this statement using proof by induction, we would show that it holds for the base case and use the inductive step to show it holds for the next value. The key steps in a proof by induction are the base case, the inductive step, and the conclusion that the statement holds for all values. This method is useful for proving statements that hold
  • #1
hangainlover
83
0

Homework Statement


I have proved the first one and I am trying to do the second using the result from part 1)


Homework Equations



[itex]F_1=1, F_2=2, F_n=F_{n-1}+F_{n-2}[/itex]

The Attempt at a Solution


base case: [itex]F_1|F_k[/itex] since[itex] F_1=1[/itex]

Assume it works for n, [itex]F_n|F_{kn}[/itex]
show [itex]F_{n+1}|F_{kn+k}[/itex]

Well, using the part 1)
[itex]F_{kn+k}=F_kF_{kn+1}+F_{k-1}F_{kn}[/itex]

That's as far as i could go..
 

Attachments

  • cc.JPG
    cc.JPG
    10.2 KB · Views: 359
Physics news on Phys.org
  • #2
I have uplloaded the problem statement in the attachment
sorry i forgot to mention that
 
Last edited:

What is "Proof by Induction Homework"?

Proof by induction is a method used in mathematics to prove statements about natural numbers or other well-ordered sets. It involves using a base case and an inductive step to show that a statement holds for all values of a given variable.

What does "F_n|F_{kn}" mean?

In this context, "F_n|F_{kn}" refers to the statement that the nth Fibonacci number divides the k*nth Fibonacci number. In other words, if n and k are both natural numbers, then the nth Fibonacci number is a factor of the k*nth Fibonacci number.

How is "Proof by Induction" used to prove "F_n|F_{kn}"?

To prove that "F_n|F_{kn}", we would use proof by induction to show that the statement holds for the base case (usually n = 1) and then use the inductive step to show that if the statement holds for n, it also holds for n+1. This would demonstrate that the statement holds for all natural numbers.

What are the key steps in a proof by induction?

The key steps in a proof by induction are as follows:

  • Base case: Show that the statement holds for the first value of the variable (usually n = 1).
  • Inductive step: Assume that the statement holds for some value of the variable (usually n), and use this to show that it also holds for the next value (n+1).
  • Conclusion: Conclude that the statement holds for all values of the variable.

Why is "Proof by Induction" a useful method for proving statements?

Proof by induction is useful because it allows us to prove statements that hold for infinitely many values. It also provides a clear and structured method for proving these types of statements, making it easier to understand and verify the validity of the proof.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
14
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
385
  • Calculus and Beyond Homework Help
Replies
1
Views
993
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
747
  • Calculus and Beyond Homework Help
Replies
1
Views
457
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
Back
Top