Contributors

* [1. 在平面上画n条无限直线，每对直线都在不同的点相交，它们构成的无限区域数记为<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>, 求<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>满足的递推关系。](#1-在平面上画n条无限直线每对直线都在不同的点相交它们构成的无限区域数记为fn-求fn满足的递推关系)
* [2. n位三进制数中，没有1出现在任何2的右边的序列的数目为<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，求<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>满足的递推关系。](#2-n位三进制数中没有1出现在任何2的右边的序列的数目为fn求fn满足的递推关系)
  * [*3. n位四进制数中，若：](#3-n位四进制数中若)
  * [4. 凸<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6667em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">2</span></span></span></span>边形中，由所有对角线分割的区域数记为<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>.假设没有三条对角线交于一点，求<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>满足的的递推关系。](#4-凸n2边形中由所有对角线分割的区域数记为fn假设没有三条对角线交于一点求fn满足的的递推关系)
  * [*5. 求n位0,1序列中"101"只出现一次且在第n位出现的序列数<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>](#5-求n位01序列中101只出现一次且在第n位出现的序列数fn)
  * [6.求解下列递推关系：](#6求解下列递推关系)
  * [(1) <span class="katex-display"><span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">9</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">2</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">9</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">3</span><span class="mclose">)</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">3</span><span class="mpunct">,</span><span class="mspace nobreak"> </span><span class="mspace nobreak"> </span><span class="mspace nobreak"> </span><span class="mspace nobreak"> </span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">0</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">2</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">2</span></span></span></span></span>](#1-fn--fn-1--9fn-2-9fn-3nge3--f00-f11f22)
  * [(3)](#3)
  * [7.求解下列递推关系：](#7求解下列递推关系)
  * [(1)<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">n</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.6644em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n</span></span></span></span></span></span></span></span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">0</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">789</span></span></span></span>](#1nfn--n-1fn-1--2nnge1-f0789)
  * [(2) <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">2</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">0</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">0</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">4</span></span></span></span>](#2-f2n--2fn-1--0nge-1-f0--4)
  * [(3) <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">n</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">n</span><span class="mclose">!</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">0</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">2</span></span></span></span>](#3-fn-nfn-1nnge-1-f0--2)
  * [8.求解下列递推关系：](#8求解下列递推关系)
  * [(1) <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">2</span><span class="mclose">)</span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">0</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span>](#1-fn--n2fn-1nge-1-f0--1)
  * [(2) <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1.3651em;vertical-align:-0.52em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.8451em;"><span style="top:-2.655em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">n</span><span class="mopen mtight">(</span><span class="mord mathnormal mtight">n</span><span class="mbin mtight">+</span><span class="mord mtight">1</span><span class="mclose mtight">)</span></span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.394em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.52em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">0</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span>](#2-fn--fn-1--frac1nn1nge-1-f0--1)
  * [(3) <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">2</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">3</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.7477em;vertical-align:-0.0833em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.6644em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">4</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord">−</span><span class="mord">1</span><span class="mclose"><span class="mclose">)</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.6644em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n</span></span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">0</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">0</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span>](#3-fn2---fn--3cdot-2n--4cdot--1n-f00-f1--1)
  * [9. 求下列n阶行列式的值](#9-求下列n阶行列式的值)
  * [10. 求解习题1~4所列出的递推关系.](#10-求解习题14所列出的递推关系)
* [11. <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7278em;vertical-align:-0.0833em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span>棋盘用红、白、蓝三种颜色进行着色，不允许相邻两格都着红色，求着色方案数满足的递推关系，并求出着色方案数。](#11-1times-n棋盘用红白蓝三种颜色进行着色不允许相邻两格都着红色求着色方案数满足的递推关系并求出着色方案数)
  * [12. 求矩阵](#12-求矩阵)

• 容易确定主对角线上的元素为$(3^n,2^n)$。
  $ {\left( \begin{matrix} 3^n & f(n) \ 0 & 2^n \end{matrix} \right)} {\left( \begin{matrix} 3 & -1 \ 0 & 2 \end{matrix} \right)}
  • 13.从1到n的自然数中选取k个不同且不相邻的数，设次选取的方案数为$f(n, k)$.
  • （1）求$f(n,k)$满足的递推关系；
  • （2）用归纳法求$f(n, k)$
  • （3）若设1与n算是相邻的数，并设在此假设下从1到n的自然数中选取k个不同且互不相邻的数的方案数为$g(n,k)$,试利用$f(n, k)$求$g(n, k)$
  • 14.利用生成函数求解下列递推关系
  • (1) $f(n) = 4f(n-2), f(0)=0, f(1)=1;$
  • (2)$f(n) = f(n-1) + 9f(n-2)-9f(n-3),n\ge3, ~~~~ f(0)=0, f(1)=1,f(2)=2$
  • 15. 设k是正整数，证明：对任意一组常数$d_1, d_2, \cdots, d_k$，表达式$\sum_{j=1}^{k}d_jC_{n+j-1}^{j-1}$可唯一地表示为一个$k-1$次多项式；反之亦然
  • 16. 某人有n元钱，她每天去菜市场买一次菜，每次买菜的品种很单调，或者买一元钱的蔬菜，或者买两元钱的猪肉，或者买两元钱的鱼。那么，她有多少种不同的方式花完这n元钱？
  • 17.在圆周上任取n个不同的点，过每两点做一条弦。假设这些弦中没有三条在圆内交于一点，令$a_n$表示这些弦将圆分成的区域数。证明：$a_n = C_n^4 + C_n^2 + 1$
  • 18. 设集合$S_n = {1, 2, \cdots, n}$，若X是$S_n$的子集，把X中所有数的和称为X的"容量"（规定空集的容量为0).若X得容量为奇（偶）数，则称X为$S_n$的奇（偶）子集。
  • 19.确定$f(n)$的一个递推关系，$f(n)$是一个平面被n个圆划分的区域数量，其中每一对圆正好相交于两点且没有三个圆相交于一点。
  • 20.求由0，1，2，3作成的含有偶数个0的n-可重复排列的个数。
  • 21. $m(m\ge2)$个人互相传球，接球后即传给别人。首先由甲发球，并把它作为第一次传球。求经过n次传球后，球又回到甲手的传球方式数

转载自liuzengh/combinatorial-mathematics

1. 在平面上画n条无限直线，每对直线都在不同的点相交，它们构成的无限区域数记为$f(n)$,求$f(n)$满足的递推关系。$f(n)=f(n-1)+n, f(1)=2~~~~ n\in N^+$

2. n位三进制数中，没有1出现在任何2的右边的序列的数目为$f(n)$，求$f(n)$满足的递推关系。$f(n) = 2f(n-1) + 2^{n-1}, f(1) = 3$

*3. n位四进制数中，若：

（1） 有偶数个0的序列共有$f(n)$个；

（2）有偶数个0且有偶数个1的序列共有$g(n)$个；求$f(n), g(n)$满足的递推关系显然当n=1,序列1，2和3含有0个0，所以$f(1) = 3$。长度为n-1序列一共有$4^{n-1}$，有偶数个0的序列共有$f(n-1)$个，有奇数个0的序列共有$4^{n-1}-f(n-1)$个。在长度为n-1且有偶数个0的序列后加入非零数(1,2,3)，得到长度为n的序列含有0的个数是偶数个，该情况一共有$3f(n-1)$;在长度为n-1且有奇数个0的序列后加入0，得到长度为n的序列含有0的个数是也是偶数,该情况一共有$4^{n-1}-f(n)$。所以$f(n) = 3f(n-1)+4^{n-1}-f(n-1) = 2f(n-1) + 4^{n-1}, f(1) = 3$显然当n=1,序列2和3含有0个0和0个1，所以$g(1) = 2$,设长度为n且有奇数个0且有奇数个1的序列共有$q(n)$。长度为n-1序列一共有$4^{n-1}$，有偶数个0且有偶数个1的序列共有$g(n-1)$，在其后分别加上2或3得到长度为n的序列含有偶数个0和偶数个1，该情况一共有$2g(n-1)$个;有偶数个0奇数个1或有奇数个0偶数个1的序列共有$4^{n-1}-g(n-1)-q(n-1)$个,在其后分别加上1或0得到长度为n的序列含有偶数个0和偶数个1，该情况一共有$4^{n-1}-g(n-1)-q(n-1)$个。所以:$g(n) = 2g(n-1) + 4^{n-1}-g(n-1)-q(n-1) = 4^{n-1} + g(n-1) - q(n-1), (1)$,同理有$q(n) = 4^{n-1} + q(n-1) - g(n-1) , (2)$，(1),(2)式子相加得到$q(n)+g(n) = 2\cdot 4^{n-1}, q(n-1) = 2\cdot 4^{n-2}-g(n-1)$，带入(1)式有$g(n) = 2g(n-1) + 2\cdot 4^{n-2}, g(1) = 2$

4. 凸$n+2$边形中，由所有对角线分割的区域数记为$f(n)$.假设没有三条对角线交于一点，求$f(n)$满足的的递推关系。$$f(n)=f(n-1)+C_{n+1}^3+n,f(1)=1$$给定一个凸$n+2$边形，将顶点集划分为两部分：顶点$X$和其余顶点$P_1, P_2, \cdots, P_{n+1}$，点$P_1,P_{n+1}$同$X$相邻。从$P_1, \cdots, P_{n+1}$中任取3个不同点构成三角形$P_iP_kP_j$,其中线段$XP_k$和$P_iP_j$相交。可以发现每次相交等同于在$P_1, P_2, \cdots, P_{n+1}$的n+1凸边形中划分出一个新的区域，总共为$C_{n+1}^3$，另外加上把三角$XP_1P_{n+1}$分割出来的n个小区域，一共为：$ f(n-1) + C_{n+1}^3+ n$

*5. 求n位0,1序列中“101“只出现一次且在第n位出现的序列数$f(n)$最后三位是“010”的n位0，1序列共有$2^{n-3}$个，包含以下情况-$f(n)$:第n位第一次出现“010”的序列数-$f(n-2)$:第n-4位到n-2为第一次出现“010”的序列数-$f(n-3)$:第n-5位到n-3为第一次出现“010”的序列数-$2f(n-4)$:第n-6位到n-4为第一次出现“010”的序列数，因为第n-3位可取0或1-$2^{i-3}f(n-1)$:当$3\le i \le n-3$时，表示在第n-i-2位到第n-i位第一次出现“010”的序列数，因为中间第n-3位都可取0或1.$f(n) = 2^{n-3}-f(n-2)-f(n-3)-2f(n-4)-\cdots-2^{n-6}f(3), n\ge6, f(3)=1, f(4)=2, f(5)=3$

6.求解下列递推关系：

(1) $$f(n)=f(n-1)+9f(n-2)-9f(n-3),n\ge 3,f(0)=0,f(1)=1,f(2)=2$x^3 -x^2 - 9x+9 = 0, (x-1)(x-3)(x+3) = 0, x_1 = -3, x_2=1, x_3 = 3c_1(-3)^n + c_2(1)^n+ c_3(3)^nc_1 + c_2 + c_3 = 0,

-3c_1+c_2 + 3c_3 = 1, 9c_1 + c_2 + 9c_3 = 2c_1 = -\frac{1}{12}, c_2=-\frac{1}{4}, c_3 = \frac{1}{3}f(n) = -\frac{1}{12}(-3)^n -\frac{1}{4} + \frac{1}{3}3^n$

(2)

$f(n) = 3f(n-2)-2f(n-3) , n \ge 3, f(0) = 1, f(1) = 0, f(2) = 0;$该递推关系的特征方程为：$x^3 - 3x+2 = 0$，即$(x-1)^2(x+2) = 0$,其特征根为:$x_1 = 1, x_2 = 1, x_3 = -2$对应$x = 1$的解为：$c_11^n+c_2n1^n = c_1+c_2n$对应$x = -2$的解为：$c_3(-2)^n$因此，递推关系的通解为：$c_1+c_2n+c_3(-2)^n$代入初始值，得到方程组$c_1 +c_3 = 1 ,, c_1+c_2-2c_3 = 0 ,, c_1 + 2c_2 + 4c_3 = 0$解得$c_1 = \frac{8}{9}, c_2 =-\frac{2}{3} ,c_3 = \frac{1}{9}$。所以原递推关系的解为：$f(n) = \frac{8}{9} -\frac{2}{3}n+ \frac{1}{9}(-2)^n$

(3)

$f(n) = 4f(n-1)-3f(n-2)+3^n, n\ge2, f(0)=1, f(1)=2x=3$是特征方程的1重根，所以特解为$an3^n$,带入递推关系有:$an3^n = 4a(n-1)3^{n-1} - 3a(n-2)3^{n-2} + 3^n$,$a = \frac{3}{2}$,相应的齐次递推关系的通解为$c_1 + c_23^n$,所以原递推关系的通解为：$\frac{3}{2}n3^n + c_1 + c_2 3^n$，$c_1 + c_2 = 1, \frac{9}{2} + c_1 + 3c_2 = 2$,$c_1 = \frac{11}{4} , c_2 = -\frac{7}{4}$,$\frac{3}{2}n3^n + \frac{11}{4} + -\frac{7}{4} 3^n$，

7.求解下列递推关系：

(1)$nf(n) + (n-1)f(n-1) = 2^n(n\ge1), f(0)=789f(n) = -\frac{n-1}{n}f(n-1) + \frac{2^n}{n} = -\frac{n-1}{n}(-\frac{n-2}{n-1}f(n-2) + \frac{2^{n-1}}{n-1}) + \frac{2^n}{n} = \frac{n-2}{n}f(n-2)-\frac{2^{n-1}}{n}+

\frac{2^n}{n} = \frac{1}{n}\sum_{i=0}^{n}(-1)^{i+1}2^i$

(2) $f^2(n) + 2f(n-1) = 0(n\ge 1), f(0) = 42ln,f(n) + ln2 + ln,f(n-1) = 0g(n) = ln,f(n), g(0) = ln,4g(n) = -\frac{1}{2}g(n-1) -\frac{ln2}{2}g(n) = (-\frac{1}{2})^nln,4 - n\frac{ln2}{2}f(n) = \frac{4^{(-\frac{1}{2})^n}}{2^{\frac{n}{2}}} = 2^{2(-\frac{1}{2})^n - \frac{n}{2}}$

(3) $f(n) =nf(n-1)+n!(n\ge 1), f(0) = 2f(n) = nf(n-1)+n! = n(n-1)f(n-2) + 2n! = 2\cdot n! + n\cdot n!$

8.求解下列递推关系：

(1) $f(n) = (n+2)f(n-1)(n\ge 1), f(0) = 1\frac{f(n)}{f(n-1)} \frac{f(n-1)}{f(n-2)} \cdot \frac{f(1)}{f(0)} f(0))= (n+2)(n+1)\cdots 3\cdot 1 =\frac{(n+2)!}{2}$

(2) $f(n) = f(n-1) + \frac{1}{n(n+1)}(n\ge 1), f(0) = 1(f(n) - f(n-1)) + (f(n-1)-f(n-2)) + \cdots + (f(1)-f(0)) + f(0) = (\frac{1}{n}-\frac{1}{n+1}) + (\frac{1}{n-1}-\frac{1}{n} ) + \cdots + (\frac{1}{1} - \frac{1}{2}) + 1 = 2 -\frac{1}{n+1}$

(3) $f(n+2) - f(n) = 3\cdot 2^n + 4\cdot (-1)^n, f(0)=0, f(1) = 1f(n) = f(n-2) + 3\cdot 2^{n-2} + 4 \cdot (-1)^{n-2} = f(n-4) + 3\cdot (2^{n-2}+2^{n-4}) + 4 \cdot ((-1)^{n-2}+(-1)^{n-4}) $当n为偶数时$f(n) = f(0) + 3\cdot (2^{n-2}+2^{n-4} +\cdots + 2^0) + 4 \cdot ((-1)^{n-2}+(-1)^{n-4} + (-1)^0) = \frac{(1-4^{n/2})}{1-4} + 4\cdot \frac{n}{2} = \frac{4^{n/2}-1}{3}+2n$当n为奇数时$f(n) = f(1) + 3\cdot (2^{n-2}+2^{n-4} +\cdots + 2^1) - 4 \cdot ((-1)^{n-2}+(-1)^{n-4} + (-1)^1) = \frac{(1-4^{(n+1)/2})}{1-4} - 4\cdot \frac{n+1}{2} = \frac{4^{(n+1)/2}-1}{3}-2n-2$

9. 求下列n阶行列式的值

$$d(n)=\left|\begin{array}{ccccccc}2& 1& 0& 0& \cdots & 0& 0\\ 1& 2& 1& 0& \cdots & 0& 0\\ 0& 1& 2& 1& \cdots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ 2& 1& 0& 0& \cdots & 2& 1\\ 2& 1& 0& 0& \cdots & 1& 2\end{array}\right|$d(n) = 2d(n-1)-d(n-2), d(1)=2, d(2)=3$

10. 求解习题1~4所列出的递推关系.

1. $f(n) = n + (n-1) + (n-2) + \cdots + 2 + f(1) = \frac{n^2+n+2}{2}$2.$f(n) = 2f(n-1)+2^{n-1}+2(f(n-2)+2^{n-2})+2^{n-1} = 2f(n-2)+2^{n-1}+2^{n-1} = 2f(n-3)+2^{n-2}+2^{n-1}+2^{n-1} = 2f(1)+2^2+\cdots+2^{n-1}+2^{n-1} = 2^n + 2^{n-1} + 2, n\ge2, f(1)=3$3.$f(n) = 2f(n-1) + 4^{n-1} = 2f(n-2)+2\cdot 4^{n-2}+4^{n-1} = 2f(1)+2\cdot(4+4^2+\cdots + 4^{n-2}) + 4^{n-1}=\frac{5}{3}4^{n-1}+\frac{10}{3} , n\ge 2f(1) = 3g(n) = 2g(n-1) + 2\cdot 4^{n-2}=2g(n-2)+2\cdot 4^{n-3}+2\cdot4^{n-2} = 2g(1)+2\cdot(4^0+4^1+\cdots + 4^{n-2})=\frac{2}{3}4^{n-1}+\frac{10}{3}, g(1) = 2$4.$f(n) = f(n-1) + C_{n+1}^3+ n = f(1) +(C_3^3 + C_4^3 + \cdots + C_{n+1}^3) + (2+3+\cdots +n) = C_{n+2}^4+C_{n+1}^2, ~~~~f(1)=1$

11. $1\times n$棋盘用红、白、蓝三种颜色进行着色，不允许相邻两格都着红色，求着色方案数满足的递推关系，并求出着色方案数。$f(n) = 2f(n-1) + 2f(n-2), f(1)=3, f(2) = 8x^2 - 2x-2 = 0, x_1 = 1-\sqrt 3, x_2 = 1+\sqrt 3$通解为:$c_1(1+\sqrt3)^n + c_2(1-\sqrt3)^n$代入初始值：$c_1(1+\sqrt3) + c_2(1-\sqrt3) = 3, c_1(4+2\sqrt3)+c_2(4-2\sqrt3)=8$解得:$c_1 = \frac{3-8\sqrt3}{18}, c_1 = \frac{3+8\sqrt3}{18}， f(n) = \frac{3-8\sqrt3}{18}(1+\sqrt3)^n + \frac{3+8\sqrt3}{18}(1-\sqrt3)^n$

12. 求矩阵

$${\left(\begin{array}{cc}3& -1\\ 0& 2\end{array}\right)}^{100}$$容易确定主对角线上的元素为$(3^n, 2^n)$。$ {\left( \begin{matrix} 3^n & f(n) \ 0 & 2^n \end{matrix} \right)} {\left( \begin{matrix} 3 & -1 \ 0 & 2 \end{matrix} \right)}

{\left( \begin{matrix} 3^{n+1} & 2f(n)+2^{n+1}-3^n \ 0 & 2^{n+1} \end{matrix} \right)} f(n+1) = 2f(n)+2^{n+1}-3^n, f(1)=-1$

13.从1到n的自然数中选取k个不同且不相邻的数，设次选取的方案数为$f(n, k)$.

考虑两种情况，选n和不选n。

（1）求$f(n,k)$满足的递推关系；$f(n, k) = f(n-1, k) + f(n-2, k-1), f(n, 1)=n, f(2k-1, k)=1$。$ f(n, k)=0, n\lt2k-1$

（2）用归纳法求$f(n, k)f(n, 1) = n = C_{n+1-1}^1, n\ge1f(n, n) = n = C_{n+1-n}^n, n\ge1 $假设$i\le j\le n, f(j, i)=C_{j+1-i}^i$成立，则：$f(n+1, k)=f(n, k) + f(n-1, k-1)=C_{n+1-k}^k + C_{n-1+1-(k-1)^{k-1}}=C_{(n+1)+1-k}^k$所以：$f(n, k) = C_{n+1-k}^k$

（3）若设1与n算是相邻的数，并设在此假设下从1到n的自然数中选取k个不同且互不相邻的数的方案数为$g(n,k)$,试利用$f(n, k)$求$g(n, k)g(n,k) = f(n-1, k) + f(n-3, k-1), g(n, 1) = n$

14.利用生成函数求解下列递推关系

(1) $f(n) = 4f(n-2), f(0)=0, f(1)=1;$A(x)-f(0)-f(1)x={\sum }_2^{\infty }f(x)x^n={\sum }_{n=2}^{\infty }4f(n-2)x^n=4x^2{\sum }_{n=0}^{\infty }f(n)x^n=4x^{2}A(x)$A(x) = \frac{1}{4}(\frac{1}{1-2x} - \frac{1}{1+2x}) = \sum_{n=0}^{\infty}\frac{1}{4}(2^n-(-2)^{n})x^n$

(2)$f(n) = f(n-1) + 9f(n-2)-9f(n-3),n\ge3, ~~~~ f(0)=0, f(1)=1,f(2)=2A(x) - f(0) - xf(1)-x^2f(2) =\sum_{n=3}^{\infty}f(n)x^n = \sum_{n=3}^{\infty}(f(n-1)+9f(n-2)-9f(n-3))x^n = x\sum_{n =2}^{\infty}f(n) + 9x^2\sum_{n =1}^{\infty}f(n) -9x^3\sum_{n =0}^{\infty}f(n) = x[A(x)-f(0)-xf(1)]+9x^2[A(x)-f(0)]-9x^3A(x)A(x) = \frac{x^2+x}{9x^3-9x^2-x+1} = \frac{1}{3}\frac{1}{1-3x} -\frac{1}{12}\frac{1}{1-(3x)} -\frac{1}{4} \frac{1}{1-x} = \sum_{n=0}^{\infty}(-\frac{1}{12}(-3)^n -\frac{1}{4} + \frac{1}{3}3^n)x^n$

(3) $f(n) = 3f(n-2)-2f(n-3) , n \ge 3, f(0) = 1, f(1) = 0, f(2) = 0;A(x) - f(0) - xf(1)-x^2f(2) =\sum_{n=3}^{\infty}f(n)x^n = \sum_{n=3}^{\infty}(3f(n-2)-2f(n-3))x^n = x^2\sum_{n =1}^{\infty}f(n) + 2x^3\sum_{n =0}^{\infty}f(n) = x[A(x)-f(0)]+A(x)A(x) = \frac{1-3x^2}{2x^3-3x^2+1} = \frac{1-3x^2}{(1-x)^2(2x+1)} = \frac{14}{9}\frac{1}{1-x}-\frac{2}{3}\frac{1}{(1-x)^2}+\frac{1}{9}\frac{1}{1-(-2x)}f(n) = \frac{14}{9} - \frac{2}{3}(n+1) + \frac{1}{9}(-2)^n = \frac{8}{9} -\frac{2}{3}n+ \frac{1}{9}(-2)^n$

15. 设k是正整数，证明：对任意一组常数$d_1, d_2, \cdots, d_k$，表达式$\sum_{j=1}^{k}d_jC_{n+j-1}^{j-1}$可唯一地表示为一个$k-1$次多项式；反之亦然把$\sum_{j=1}^{k}d_jC_{n+j-1}^{j-1}$展开，其中$C_{n+j-1}^{j-1}$对应了一个$j-1$次多项式，所以$j=k$时就表示一个$k-1$次多项式。反过来，由于对于$k-1$次多项式，$d_1, d_2, \cdots, d_k$可以取适当数作为$C_{n+j-1}^{j-1}$的系数。

16. 某人有n元钱，她每天去菜市场买一次菜，每次买菜的品种很单调，或者买一元钱的蔬菜，或者买两元钱的猪肉，或者买两元钱的鱼。那么，她有多少种不同的方式花完这n元钱？

$f(n) = f(n-1) + 2f(n-2), f(1) = 1, f(2) = 3$特征方程：$x^2-x-2=0, x_1=-1, x_2=2$通解：$c_1(-1)^n + c_22^n$带入初始值：$-c_1 + 2c_2 = 1, c_1 + 4c_2 = 3, c_1=\frac{1}{3}, c_2 = \frac{2}{3}$解为：$\frac{1}{3}(-1)^n + \frac{2}{3}2^n f(n) = f(n-1) + C_{n+1}^3+ n = f(1) +(C_3^3 + C_4^3 + \cdots + C_{n+1}^3) + (2+3+\cdots +n) = C_{n+2}^4+C_{n+1}^2, ~~~~f(1)=1$

17.在圆周上任取n个不同的点，过每两点做一条弦。假设这些弦中没有三条在圆内交于一点，令$a_n$表示这些弦将圆分成的区域数。证明：$a_n = C_n^4 + C_n^2 + 1$参考习题4设凸$n+2$边形中，由所有对角线分割的区域数记为$f(n) = f(n-1) + C_{n+1}^3+ n, ~~~~f(1)=1$,则$a_n = f(n-2)+na_n= C_{n}^4+C_{n-1}^2+n = C_n^4 + C_n^2 + 1$

18. 设集合$S_n = {1, 2, \cdots, n}$，若X是$S_n$的子集，把X中所有数的和称为X的"容量"（规定空集的容量为0).若X得容量为奇（偶）数，则称X为$S_n$的奇（偶）子集。

（1）求证：$S_n$的奇子集和偶子集个数相等；记$A_n, B_n$分别为$S_n$得奇子集和偶子集。则：$A(n+1) = A(n)+B(n), B(n+1) = A(n)+B(n), A(1)=B(1) = 1, n为偶数A(n+1) = A(n)+A(n), B(n+1) = B(n)+B(n), A(1)=B(1) = 1, n为奇数$由此可得$A(n) = B(n)$

（2）求证: 当$n\ge 3$时，$S_n$的所有奇子集的容量之和和所有偶子集的容量之和相等；记$f(n), g(n)$分别为$S_n$的所有奇子集的容量之和和所有偶子集的容量之和。则：$f(n+1) = f(n)+(n+1)B(n)+g(n), g(n+1) = g(n)+(n+1)A(n)+f(n), f(1)=1, g(1) = 0, n为偶数f(n+1) = f(n)+(n+1)A(n)+f(n), g(n+1) = g(n)+(n+1)B(n)+g(n), f(1)=1, g(1) = 0, n为奇数f(2)=1+2\times1+1 = 4, g(2)=0+2\times1+0=2f(3)=4+3\times2+2 = 12, g(3)=2+3\times2+4=12f(3)=g(3), A(n)=B(n)$,再由上述对称递推关系式可得:$f(n) = g(n)$

（3）求$S_n (n\ge 3)$的所有奇子集的容量之和。记$t(n)$为$S_n$所有子集的容量之和。则：$t(n+1) = t(n) + (n+1)|S| = t(n) = 2t(n) + (n+1)2^n, t(3)=24$因为当$n\ge 3$时，$S_n$的所有奇子集的容量之和和所有偶子集的容量之和相等，所以$S_n (n\ge 3)$的所有奇子集的容量之和为：$\frac{t(n)}{2}$

19.确定$f(n)$的一个递推关系，$f(n)$是一个平面被n个圆划分的区域数量，其中每一对圆正好相交于两点且没有三个圆相交于一点。参考习题1$f(n) = f(n-1)+2n, f(1) = 2$

20.求由0，1，2，3作成的含有偶数个0的n-可重复排列的个数。

$f(n) = 3f(n-1) + (4^n - f(n-1)), f(1) = 3$

21. $m(m\ge2)$个人互相传球，接球后即传给别人。首先由甲发球，并把它作为第一次传球。求经过n次传球后，球又回到甲手的传球方式数第$n-2$手传给甲和不传给甲。$a_n = (m-1)a_{n-2} + (m-2)((m-1)^{n-2} - a_{n-2}), a_1=0, a_2=m-1$