i need to proof this upperbound:
"Call $p(n)$ the number of partitions of n (integer) and $F_n$ the $n-th$ Fibonacci number. Show that $p(n)\leq p(n-1) + p(n-2)$ and that $p(n)\leq F_n$ for $n\geq 2$"
Now i searched a little bit on through questions here and i found this The number of partitions of $n$ and the $n$th Fibonacci number. where the second bound is prooved asimptotically but this is not my case. Plus passing from the first inequality i have to the second one is just a matter of saying that the sum of the two $p(n-1)+p(n-2)$ is just the $n-th$ Fibonacci number or i need to say something more ? (i think yes). Anyway my idea was to use the famous relation $p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)...$ and so on but i can't get it straight forward from this. Any hint?
Notations: $F_0=0, \space F_1=1, \space F_{n+1}=F_{n}+F_{n-1}$. $p(n|"condition")=|\begin{Bmatrix} partitions \space of \space n \space verifying \space "condition" \end{Bmatrix}|$.
At first I think that you second inequality is false because $p(2)=2$ and $F_2=1$, so I will consider that the second inequality is $p(n) \le F_{n+1}$ for $n\geq1$.
We can notice that if the first inequality is true then the second is also true. Indeed by induction : $$p(1)=1 \le 1=F_2$$ Suppose that the property is true for a certain $n\geq1$, let's show that it is also true for $n+1$: $$p(n) \le p(n-1)+p(n-2) \le F_{n-1}+F_n=F_{n+1}$$ So by induction, $\bbox[5px,border:2px solid green]{p(n) \le F_{n+1}}$ for $n\geq1$.
Let's prove the first inequality. $$p(n)=p(n|with \space a \space part \space 1)+p(n|without \space a \space part \space 1)=p(n-1)+p(n|without \space a \space part \space 1)$$ $$p(n-2)=p(n|with \space a \space part \space 2)$$ So we need to prove that : $$p(n|without \space a \space part \space 1) \le p(n|with \space a \space part \space 2)$$ We consider a partition of $n$ without a part 1: $$\lambda_1+\lambda_2+...+\lambda_k,\space \forall i, \space \lambda_i \geq 2 , \space \lambda_k \space being \space the \space smallest \space part$$ We can transform it into a unique partition with at least 1 part 2 by cutting the smallest part (which is $\geq 2$) into one 2-part and 0 or more 1-part. Thus we obtain : $$\lambda_1+\lambda_2+...+\lambda_{k-1}+2+1+...+1 \space or \space \lambda_1+\lambda_2+...+\lambda_{k-1}+2$$ Then we merge all 1-parts and 1 2-part in order to have a partition with no 1-part. So we have : $$p(n-2)=p(n|without \space a \space part \space 1)+p(n|smallest \space non \space 1part \space is < 2+number\space of \space 1part)$$ The last term is always non-negative, so : $$p(n|without \space a \space part \space 1) \le p(n|with \space a \space part \space 2)$$ Finally : $$\bbox[5px,border:2px solid green]{p(n) \le p(n-1)+p(n-2)}$$