3. Recall that a composition of a positive integer n is a way of writing n as a sum of positive integers, called parts, which may appear in any order. It turns out to be interesting to count the number of compositions of n using only odd parts. Here is a table for small values of n: n 1 2 3 4 5 compositions of n with only odd parts 1 1+1 3, 1+1+1 3+1, 1+3, 1+1+1+1 5, 3+1+1, 1+3+1, 1+1+3, 1+1+1+1+1 In class we showed that each composition of n comes from a composition of n - 1 by doing one of two things: 2 1. adding 1 as a new last part 2. adding 1 to the current last part The first operation still gets us from a composition of n-1 with all parts odd to a composition of n with all parts odd. The second operation fails, but there is a replacement: add 2 to the current last part of a composition of n - 2 with all parts odd. Thus, for example, the compositions of 5 above with last part 1 come from adding 1 as a new last part to the compositions of 4 above. The compositions of 5 above whose last part is not 1 come from adding 2 to the last part of the compositions of 3 above. Recall that the Fibonacci numbers are defined by Fn+1 = Fn + Fn-1 for n ≥ 1, with Fo = 0 and F₁ = 1. Prove by induction that the number of compositions of n with all parts odd is Fn.
3. Recall that a composition of a positive integer n is a way of writing n as a sum of positive integers, called parts, which may appear in any order. It turns out to be interesting to count the number of compositions of n using only odd parts. Here is a table for small values of n: n 1 2 3 4 5 compositions of n with only odd parts 1 1+1 3, 1+1+1 3+1, 1+3, 1+1+1+1 5, 3+1+1, 1+3+1, 1+1+3, 1+1+1+1+1 In class we showed that each composition of n comes from a composition of n - 1 by doing one of two things: 2 1. adding 1 as a new last part 2. adding 1 to the current last part The first operation still gets us from a composition of n-1 with all parts odd to a composition of n with all parts odd. The second operation fails, but there is a replacement: add 2 to the current last part of a composition of n - 2 with all parts odd. Thus, for example, the compositions of 5 above with last part 1 come from adding 1 as a new last part to the compositions of 4 above. The compositions of 5 above whose last part is not 1 come from adding 2 to the last part of the compositions of 3 above. Recall that the Fibonacci numbers are defined by Fn+1 = Fn + Fn-1 for n ≥ 1, with Fo = 0 and F₁ = 1. Prove by induction that the number of compositions of n with all parts odd is Fn.
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
Transcribed Image Text:3. Recall that a composition of a positive integer n is a way of writing
n as a sum of positive integers, called parts, which may appear in any order.
It turns out to be interesting to count the number of compositions of n using
only odd parts. Here is a table for small values of n:
n
1
2
3
4
5
compositions of n with only odd parts
1
1+1
3, 1+1+1
3+1, 1+3, 1+1+1+1
5, 3+1+1, 1+3+1, 1+1+3, 1+1+1+1+1
In class we showed that each composition of n comes from a composition
of n - 1 by doing one of two things:
1. adding 1 as a new last part
2. adding 1 to the current last part
2
The first operation still gets us from a composition of n-1 with all parts
odd to a composition of n with all parts odd. The second operation fails,
but there is a replacement: add 2 to the current last part of a composition
of n 2 with all parts odd. Thus, for example, the compositions of 5 above
with last part 1 come from adding 1 as a new last part to the compositions
of 4 above. The compositions of 5 above whose last part is not 1 come from
adding 2 to the last part of the compositions of 3 above.
Recall that the Fibonacci numbers are defined by
Fn+1
=
Fn+Fn-1 for n ≥ 1, with Fo= 0 and F₁ = 1.
Prove by induction that the number of compositions of n with all parts odd
is Fn.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps with 2 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
