3

I have to determine whether the following definition is valid and, if so, find a formula for $f(n)$.

$f(0)=1$, $f(1)=0$, $f(2)=2$, $f(n)=2f(n-3)$ for $n \geq 3$

I know it is valid because I successfully get a result for $f(3)$, $f(4)$, $f(5)$ and so on from such a definition. I have also devised a formula which includes $2$ cases:

$f(n) = 0$ when $(n \bmod 3) = 1$ and $f(n) = 2^{\lceil n/3 \rceil}$ otherwise.

Now, the exercise asks to prove the formula and I see that I have to do it considering the $2$ separate cases and I guess that I can use strong induction. In fact, I am trying to use strong induction to prove the first case but I am not sure about how to do it.

So, the proposition $P(n)$ can be: $f(n) = 0$ when $(n \bmod 3) = 1$ for $n = 1, 4, 7, 10,...$ The Basis Step can be $f(1) = 0$, $f(4) = 0$, $f(7) = 0$ and then would come the Inductive Step. My question is about the Basis Step, I am not sure if it is defined correctly or if I should use a kind of recursive expression which is the subject in the book.

I will very much appreciate your advice.

Marc van Leeuwen
  • 115,048
JORGE
  • 341

2 Answers2

1

A general sketch:

Write the first few terms: $f_{0} = 1, f_{1} = 0, f_{2} = 2, f_{3} = 2, f_{4} = 0, f_{5} = 4, f_{6} = 4, \cdots$. Now by inspection the general cases can be seen: for $n \geq 0$ , $f_{3n+1} = 0, f_{3n+2} = 2^{n+1}, f_{3n+3} = 2^{n+1}.$

Leucippus
  • 26,329
  • The exercise asks to prove the formula so I still need to prove the second case which includes f(3n+2) and f(3n+3) "together". What I see is that f(3n+1), f(3n+2) and f(3n+3) for n >= 0 do not include f(0) = 1. What can I do for the case of f(0)=1? – JORGE Mar 16 '15 at 18:10
0

You are correct, I think you can simply prove $f(3n+1) = 0$ for all integers $n \ge 0$.

Base case $n=0, f(1)=0$ is true.

Assume $n=k$ is true, i.e. $f(3k+1)$ is true, then prove when $n=k+1$, $f(3k+4)$ is also true. If so, then the statement "$f(3n+1) = 0$ for all integers $\ge 0$" is always true.

Edit: Unless in your proof you need to make use of $f(3k-2)$ and/or $f(3k-5)$, a traditional mathematical induction as above is sufficient. In case $f(3k-2)$ and/or $f(3k-5)$ is involved, then yes, your basis cases will have to include the $n=1$ and $n=2$ cases (i.e. $f(4)=0$ and $f(7)=0$), and a strong induction is needed (i.e. assume $n \le k$ is true instead of $n = k$ is true).

LaBird
  • 1,018
  • This is my conclusion, please let me know if it is correct. I took f(3n+1)=0 for n>=0. I set the Basis Step as f(1)=0, f(4)=0 and f(7)=0 taking n=1,2,3. Next, for the Inductive Step, I defined that P(3j+1) is true for 0<=j<=3k+1 for k >= 2. So, what I have to prove is the conditional statement "if P[3(j+1)+1] then P[3(j-2)+1] or if P(3j+4) then P(3j-5) for j>=2". This conditional statement "relates" f(10) with f(1), f(13) with f(4), and so on. Is this enough to conclude that the proof is complete? If so, how should I write the conclusion? – JORGE Mar 16 '15 at 16:31
  • I think it is enough to conclude the proof, and you can conclude that "since $n=0, 1, 2$ are all true, and now $n=j-2$ is true implies $n=j+1$ is true for all $j\ge 2$, therefore by the principle of mathematical induction, $n=j$ is true for all integers $n>0$". The only problem is: Why do you write the condition as "$0 \le j \le 3k+1$"? $k$ already serves the same purpose as your $j$, so "$0 \le j \le n$ for $n \ge 2$" will be good enough. – LaBird Mar 16 '15 at 16:50
  • Should be "... by the principle of mathematical induction, $P(n)$ is true for all integers $n \ge 0$". – LaBird Mar 16 '15 at 17:02