MathDB

A1

Part of 1958 November Putnam

Problems(1)

Putnam 1958 November A1

Source: Putnam 1958 November

7/19/2022
Let f(m,1)=f(1,n)=1f(m,1)=f(1,n)=1 for m≥1,n≥1m\geq 1, n\geq 1 and let f(m,n)=f(m−1,n)+f(m,n−1)+f(m−1,n−1)f(m,n)=f(m-1, n)+ f(m, n-1) +f(m-1 ,n-1) for m>1m>1 and n>1n>1. Also let S(n)=∑a+b=nf(a,b)      a≥1  and   b≥1. S(n)= \sum_{a+b=n} f(a,b) \,\,\;\; a\geq 1 \,\, \text{and} \,\; b\geq 1. Prove that S(n+2)=S(n)+2S(n+1)    for  n≥2.S(n+2) =S(n) +2S(n+1) \,\, \; \text{for} \, \, n \geq 2.
Putnamfunctionrecurrence relation