这个问题本身没有严格地阐述清楚,所以不会有严格的答案.
主要问题出在两个概念“递推公式”和"通项公式",这两个概念本质上讲没有严格定义过.
粗略一点讲,递推公式大致是对任何正整数n,存在n元函数f_n使得a(n)=f_n(a(0),a(1),...,a(n-1))；通项公式则大致是说存在实变函数f使得a(n)=f(n).
我为什么要说“大致”,前者可能并没有涵盖所有可能的“递推”,这取决于需求,而后者更是一句废话,数列本就是自然数集上的函数,当然可以延拓到实数集.在通常的意义下更重要的则是这两个大致叙述中函数的选择范围,比如多项式、初等函数、代数函数、或者是很大的常用函数空间.
如果对函数空间限制比较紧,一般来讲是不保证有通项公式的.举一些最简单的例子：
(1) 如果限制函数空间为多项式,那么等比数列a(n)=a(n-1)*c就没有通项公式.
(2) 如果把条件限制在初等函数上,a(n)=a(n-1)*n,a(0)=1的通项公式是a(n)=n!,但是这个不是初等函数,也未必存在初等通项公式.
(3)另一个例子是调和级数的部分和H(n)=H(n-1)+1/n,H(0)=0,这个序列是很多中学生会问的,其通项也不是初等的,但是确实可以用超越函数来表示这个通项.
不过即便把函数空间放宽到各种常用函数及其积分或其它各种古怪的东西,只要不是最大的函数空间,仍然不容易保证"通项公式"的存在性,此时的证明并不容易,一般需要近世代数的工具,而且至少是先要严格叙述.比如“一元五次方程没有求根公式”的严格叙述是"一元五次方程的根不能用系数的有限次加减乘除和开方来表示",只有把问题叙述严格了才能进行证明.