- #1
IHateFactorial
- 17
- 0
We define a function T : \(\displaystyle \Bbb{N}\) -> \(\displaystyle \Bbb{N}\), such that \(\displaystyle T(2k+1) = 2k+2\) and \(\displaystyle T(2k) =k\). Also, \(\displaystyle T^2(n)=T(T(n))\), and generally: \(\displaystyle T^k(n)={T}^{k-1}(T(n))\).
a) Prove that for every \(\displaystyle n\in\Bbb{N}\), there exists a positive integer k, such that \(\displaystyle T^k(n)=1\)
b) We say \(\displaystyle {c}_{k}\) is the number of elements in the set:
{\(\displaystyle n:T^k(n)=1\)}
Prove that \(\displaystyle {c}_{k+2}={c}_{k+1}+{c}_{k}\), for all \(\displaystyle 1\le k\).
a) We can begin by defining the function T as
\(\displaystyle T(n)=n+1\), if n is odd, and
\(\displaystyle T(n)=\frac{n}{2}\), if n is even.
Therefore, we begin at k=0 and n being some natural. If n is even, we begin by dividing by 2 until n is odd or 1, in which case we are done. We add 1 to k everytime we divide by 2. We call the number left over by dividing 2 (or the original in case it wasn't even) \(\displaystyle {d}_{0}\).
We define a function \(\displaystyle f(x) : \Bbb{N}\) -> \(\displaystyle \Bbb{N}; f(2x+1)=T^2(2x+1)=x+1\). From here we can see that f(x) will always give a value less than the original while still providing a natural number, for all 2x+1>1.
We run d through f(x) and we add 2 to k. We call the output \(\displaystyle {d}_{1}\).
\(\displaystyle {d}_{1}\) can be either odd or even. We divide \(\displaystyle {d}_{1}\) by 2 until it is odd or one, again. Each time we do so, we add 1 to k.
We can see a recurring pattern forming. \(\displaystyle {d}_{i}\) Will continue to become smaller and smaller until it is the smallest possible natural: 1.
b) We see that \(\displaystyle {c}_{1}\) = 1. {2}
\(\displaystyle {c}_{2}\) = 2. {1, 4}
\(\displaystyle {c}_{3}\) = 3. {2, 3, 8}
\(\displaystyle {c}_{4}\) = 5 {1, 4, 6, 7, 16}
We conclude two things:
The number of even numbers in set \(\displaystyle {c}_{k+1}\) is equal to the number of elements in \(\displaystyle {c}_{k}\). This is because every even number in \(\displaystyle {c}_{k}\) comes from one number in \(\displaystyle {c}_{k-1}\). (We denote the number of even numbers in \(\displaystyle {c}_{k}\) as \(\displaystyle {e}_{k}\)).
\(\displaystyle {e}_{k+1}\) = \(\displaystyle {c}_{k}\)
The number of elements in \(\displaystyle {c}_{k+1}\) equals double the number of even numbers in the last set plus the number of odds in the last set. Reason: Each even number "leads" to two numbers (an odd and an even) and every odd number leads to an even. (We denote the number of odds in \(\displaystyle {c}_{k}\) as \(\displaystyle {o}_{k}\)).
\(\displaystyle 2{e}_{k}+{o}_{k}={c}_{k+1}\)With these defintions:
\(\displaystyle {c}_{k+2}={c}_{k+1}+{c}_{k}\)
\(\displaystyle 2{e}_{k+1}+{o}_{k+1}={e}_{k+1}+{o}_{k+1}+{c}_{k}\)
\(\displaystyle {e}_{k+1}={c}_{k}\)
The above step is an identity and such, it is proven.
a) Prove that for every \(\displaystyle n\in\Bbb{N}\), there exists a positive integer k, such that \(\displaystyle T^k(n)=1\)
b) We say \(\displaystyle {c}_{k}\) is the number of elements in the set:
{\(\displaystyle n:T^k(n)=1\)}
Prove that \(\displaystyle {c}_{k+2}={c}_{k+1}+{c}_{k}\), for all \(\displaystyle 1\le k\).
a) We can begin by defining the function T as
\(\displaystyle T(n)=n+1\), if n is odd, and
\(\displaystyle T(n)=\frac{n}{2}\), if n is even.
Therefore, we begin at k=0 and n being some natural. If n is even, we begin by dividing by 2 until n is odd or 1, in which case we are done. We add 1 to k everytime we divide by 2. We call the number left over by dividing 2 (or the original in case it wasn't even) \(\displaystyle {d}_{0}\).
We define a function \(\displaystyle f(x) : \Bbb{N}\) -> \(\displaystyle \Bbb{N}; f(2x+1)=T^2(2x+1)=x+1\). From here we can see that f(x) will always give a value less than the original while still providing a natural number, for all 2x+1>1.
We run d through f(x) and we add 2 to k. We call the output \(\displaystyle {d}_{1}\).
\(\displaystyle {d}_{1}\) can be either odd or even. We divide \(\displaystyle {d}_{1}\) by 2 until it is odd or one, again. Each time we do so, we add 1 to k.
We can see a recurring pattern forming. \(\displaystyle {d}_{i}\) Will continue to become smaller and smaller until it is the smallest possible natural: 1.
b) We see that \(\displaystyle {c}_{1}\) = 1. {2}
\(\displaystyle {c}_{2}\) = 2. {1, 4}
\(\displaystyle {c}_{3}\) = 3. {2, 3, 8}
\(\displaystyle {c}_{4}\) = 5 {1, 4, 6, 7, 16}
We conclude two things:
The number of even numbers in set \(\displaystyle {c}_{k+1}\) is equal to the number of elements in \(\displaystyle {c}_{k}\). This is because every even number in \(\displaystyle {c}_{k}\) comes from one number in \(\displaystyle {c}_{k-1}\). (We denote the number of even numbers in \(\displaystyle {c}_{k}\) as \(\displaystyle {e}_{k}\)).
\(\displaystyle {e}_{k+1}\) = \(\displaystyle {c}_{k}\)
The number of elements in \(\displaystyle {c}_{k+1}\) equals double the number of even numbers in the last set plus the number of odds in the last set. Reason: Each even number "leads" to two numbers (an odd and an even) and every odd number leads to an even. (We denote the number of odds in \(\displaystyle {c}_{k}\) as \(\displaystyle {o}_{k}\)).
\(\displaystyle 2{e}_{k}+{o}_{k}={c}_{k+1}\)With these defintions:
\(\displaystyle {c}_{k+2}={c}_{k+1}+{c}_{k}\)
\(\displaystyle 2{e}_{k+1}+{o}_{k+1}={e}_{k+1}+{o}_{k+1}+{c}_{k}\)
\(\displaystyle {e}_{k+1}={c}_{k}\)
The above step is an identity and such, it is proven.