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.
Algebra: Structure And Method, Book 1
(REV)00th Edition
ISBN:9780395977224
Author:Richard G. Brown, Mary P. Dolciani, Robert H. Sorgenfrey, William L. Cole
Publisher:Richard G. Brown, Mary P. Dolciani, Robert H. Sorgenfrey, William L. Cole
Chapter11: Rational And Irrational Numbers
Section11.8: Adding And Subtracting Radicals
Problem 5E
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
Algebra: Structure And Method, Book 1
Algebra
ISBN:
9780395977224
Author:
Richard G. Brown, Mary P. Dolciani, Robert H. Sorgenfrey, William L. Cole
Publisher:
McDougal Littell
Algebra & Trigonometry with Analytic Geometry
Algebra
ISBN:
9781133382119
Author:
Swokowski
Publisher:
Cengage
Algebra: Structure And Method, Book 1
Algebra
ISBN:
9780395977224
Author:
Richard G. Brown, Mary P. Dolciani, Robert H. Sorgenfrey, William L. Cole
Publisher:
McDougal Littell
Algebra & Trigonometry with Analytic Geometry
Algebra
ISBN:
9781133382119
Author:
Swokowski
Publisher:
Cengage
Holt Mcdougal Larson Pre-algebra: Student Edition…
Algebra
ISBN:
9780547587776
Author:
HOLT MCDOUGAL
Publisher:
HOLT MCDOUGAL
