0

I am wondering why $f(n)$ is even why $3|n$. I can only prove that $f(n)$ is even when $n=3\cdot 2^k$ because $f(3)$ is even.

rd142857
  • 23
  • Welcome to [math.se] SE. Take a [tour]. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an [edit]): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. – Another User Jul 05 '22 at 15:03
  • What is $f(4)$? – Henry Jul 05 '22 at 15:09
  • 1
    Not sure I understand the question. Are you claiming that $3,|,n\implies f(n)$ even? But $f(6)=3$, right? Did you mean to say $f(2n)=f(n)$ or something like that? – lulu Jul 05 '22 at 15:18
  • 2
    See https://oeis.org/A002487 – lhf Jul 05 '22 at 16:07

1 Answers1

1

We have, $f(1)=1$, $f(2n)=f(n)$, $f(2n+1)=f(n)+f(n+1)$

We will prove that $f(n)$ is even when $3|n$, odd otherwise by induction.

Suppose the above claim holds for all $k<n$.

If,
$n=6m$, $f(n) = f(3m)$, hence $f(n)$ is even
$n=6m+3$, $f(n) = f(3m+1)+f(3m+2)$, hence $f(n)$ is even.

If,
$n=6m+1$, $f(n) = f(3m) + f(3m+1)$, hence $f(n)$ is odd
$n=6m+2$, $f(n) = f(3m+1)$, hence $f(n)$ is odd
$n=6m+4$, $f(n) = f(3m+2)$, hence $f(n)$ is odd
$n=6m+5$, $f(n) = f(3m+2) + f(3m+3)$, hence $f(n)$ is odd.

Hence the claim is true for n.

Since the claim is true for all positive integers less than 2, the proof follows by induction.

ksnad
  • 66