title: How to make DifferenceRoot and RecurrenceTable useful for non-numeric difference equations?
body: <p>In answering <a href="http://www.physicsforums.com/showthread.php?t=521314" rel="nofollow">a physics forum question</a> this morning, I ran into really bad performance of <code>DifferenceRoot</code> and <code>RecurrenceTable</code> compared to calculating the expressions by naively taking derivatives of an exponential generating functional.  A very small amount of digging showed that <code>DifferenceRoot</code> and <code>RecurrenceTable</code> <em>do not simplify expressions as they go</em>.</p>
  
  <p>For example, look at the following output of <code>RecurrenceTable</code> and how it simplifies by just <code>Expand</code>ing the result:</p>
  
  <pre><code>In[1]:= RecurrenceTable[f[n] == a f[n - 1] + (a - 1) f[n - 2] &amp;&amp; 
                          f[0] == 0 &amp;&amp; f[1] == 1, 
                          f, {n, 6}]
  % // Expand
  
  Out[1]= {0, 1, a, -1+a+a^2, -a+a^2+a (-1+a+a^2), 1-a-a^2+a (-1+a+a^2)+a (-a+a^2+a (-1+a+a^2))}
  Out[2]= {0, 1, a, -1+a+a^2, -2 a+2 a^2+a^3, 1-2 a-2 a^2+3 a^3+a^4}
  </code></pre>
  
  <p>This quickly gets out of hand, as the leaf count of the 20th iteration (calculated using  <code>DifferenceRoot</code>) shows:</p>
  
  <pre><code>dr[k_] := DifferenceRoot[Function[{f, n}, 
            {f[n] == a f[n - 1] + (a - 1) f[n - 2], f[0] == 0, f[1] == 1}]][k]
  
  In[2]:= dr20 = dr[20]; // Timing
          dr20Exp = Expand[dr20]; // Timing
  Out[2]= {0.26, Null}
  Out[3]= {2.39, Null}
  
  In[4]:= {LeafCount[dr20], LeafCount[dr20Exp]}
  Out[4]= {1188383, 92}
  </code></pre>
  
  <p>Which can be compared to the <a href="http://en.wikipedia.org/wiki/Memoization" rel="nofollow">memoized</a> implementation</p>
  
  <pre><code>In[1]:= mem[n_] := a mem[n-1] + (a-1) mem[n-2] // Expand
          mem[0] = 0; mem[1] = 1;
  
  In[3]:= mem20 = mem[20];//Timing
          LeafCount[mem20]
  Out[3]= {0.48, Null}
  Out[4]= 92
  </code></pre>
  
  <p><strong>So my question is:</strong>
  Are there any options/tricks to get <code>DifferenceRoot</code> and <code>RecurrenceTable</code> to apply a (simplifying) function as they go and thus make them useful for non-numeric work?</p>
  
  <p><strong>Edit:</strong> A Sjoerd pointed out below, I foolishly chose an example with a <code>RSolve</code>able closed form solution. In this question I'm primarily concerned with the behaviour of <code>DifferenceRoot</code> and <code>RecurrenceTable</code>. If it helps, imagine the the <code>f[n-2]</code> term is multiplied by <code>n</code>, so that there is no simple closed form solution.</p>