Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

I have a problem, for which the solution(by looking at the pattern) I found is

$$f(n)=\begin{cases}2n-3,\text{if }n<4\\2n-4,\text{if }n\ge 4\;.\end{cases}$$

I want to prove it inductively, I'm confused as to where do I begin? I know the basic induction proving it for $n=1$, assuming it true for $n=1,\dots,n-1$, and then proving it for $n=n$.

The problem is here $f(n)$ for $n=1$ is different and for $n-1$ (if greater than $3$ it will be different). If someone can guide me... how do I go on proving this thing.

Update: I have heard that induction works because we prove it for n=1, assume it true for n=1... n-1 and then prove it for n=n... which works because proving it for n=n is similar to n=1 and it again proves for n=(n+1)... (2n-1), we keep on going like that.

share|improve this question
2  
You would prove cases $n=1,2$, and $3$ separately and then prove the case $n\ge 4$ by induction starting at $n=4$ as your base case. A proof by induction need not start at $1$. – Brian M. Scott Apr 12 '12 at 0:44
I thought that but I heard that when we prove it for n.. it basically rounds back to n=1(intuitively) and since we have already proved n=1, its proved for all the numbers. – questions Apr 12 '12 at 0:46
That dispayed version of $f(n)$ is exactly equivalent to your original two-line statement. I don’t understand your other comment; perhaps you should add the original problem to your question. – Brian M. Scott Apr 12 '12 at 0:49
Due to some reason, the formatting is not showing up in firefox.. and I have updated the question. – questions Apr 12 '12 at 0:50
@questions: If you really insist on starting at $1$ (and you definitely should not), let $g(n)=f(n+3)$. You can show by induction on $m$ that $g(m)=2(m+3)-4$ for all $m\ge 1$. But to repeat what others have said, use as base case $n=4$. – André Nicolas Apr 12 '12 at 3:41
show 2 more comments

closed as not a real question by Lord_Farin, O.L., Martin, Amzoti, Asaf Karagila May 22 at 22:48

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

Browse other questions tagged or ask your own question.