染色问题递推公式

高中数学竞赛讲座二试内容19

染色问题 （一）

一．基本方法

染色问题的本质是对集合的元素进行分类的问题，染色可以使分类更直观、更形象．

染色问题主要有两类：一类使借助染色方法解决问题；二类是问题的条件是用染色的方式给出的．常

见的染色问题有对区域的染色（包括对方格，三角形的染色），对线段的染色，对点的染色．常用思想方法是整体思想，抽屉原理，考虑极端情形，数学归纳法，构造思想等． 二．例题精选

（一）．k染色平面问题

将平面上的点用不超过k种颜色给每一个点染一种颜色，这样的平面叫做k染色平面．

１．坐标平面上若干个整点，将一些整点染红色，一些染蓝色，证明：总可以有一种染法使每行、每列两

种颜色点数之差不超过１．

R B R R B B R B B R B R B R R B R B R B

R B R B R

B R B R B

２．对于任意的a>0，二染色平面上必存在斜边长为a且内角分别为30?,60?,90?的三顶点同色的三角形．

B B

Ｒ a Ｒ

３．将平面上每一个点都以红、蓝两色之一染色，证明：存在这样的两个相似三角形，

B B 它们相似比为１９９５，而且每个三角形的三个顶点同色．

1

B B R RR

高中数学竞赛讲座二试内容19

染色问题 （一）

一．基本方法

染色问题的本质是对集合的元素进行分类的问题，染色可以使分类更直观、更形象．

染色问题主要有两类：一类使借助染色方法解决问题；二类是问题的条件是用染色的方式给出的．常

见的染色问题有对区域的染色（包括对方格，三角形的染色），对线段的染色，对点的染色．常用思想方法是整体思想，抽屉原理，考虑极端情形，数学归纳法，构造思想等． 二．例题精选

（一）．k染色平面问题

将平面上的点用不超过k种颜色给每一个点染一种颜色，这样的平面叫做k染色平面．

１．坐标平面上若干个整点，将一些整点染红色，一些染蓝色，证明：总可以有一种染法使每行、每列两

种颜色点数之差不超过１．

R B R R B B R B B R B R B R R B R B R B

R B R B R

B R B R B

２．对于任意的a>0，二染色平面上必存在斜边长为a且内角分别为30?,60?,90?的三顶点同色的三角形．

B B

Ｒ a Ｒ

３．将平面上每一个点都以红、蓝两色之一染色，证明：存在这样的两个相似三角形，

B B 它们相似比为１９９５，而且每个三角形的三个顶点同色．

1

B B R RR

Just do it !

常见递推数列通项公式的求法

类型一：an?1?kan?b

（1）累加法：k?1时，an?1?an?b?{an}是等差数列，an?b?n?(a1?b)

例1：已知{an}的首项a1?1，an?1?an?2n（n?N*）求通项公式。

解：an?an?1?2(n?1)

an?1?an?2?2(n?2)

an?2?an?3?2(n?3)…… a3?a2?2?2

?a2?a1?2?1

an?a1?2[1?2???(n?1)]?n2?n

∴ a2n?n?n?1

（2）待定系数法：k?1时，设an?1?m?k(an?m)

∴ an?1?kam?bn?km?m，比较系数：km?m?b，、∴

k?1，

∴

{an?bk?1}是等比数列，公比为k，首项为ab1?k?1

1 ∴

an?bk?1?(abbb1?k?1)?kn? ∴

an?(a1?k?1)?kn?1?k?1 例2：已知{an}满足a1?3，an?1?2an?1求通项公式。

解：设an?1?m?2(an?m) an?1?2an?m ∴ m?1 ∴ {an?1?1}是以4为首项，2为公比为等比数列 ∴ an?1n?1?4?2

16染色问题

染色是将一组对象进行分类的一种直观描述. 例如，我们将集合A中的一部分元素染成红色，另一部分元素染成兰色，再把剩下的元素全染成黄色，这时我们就把集合的元素分成了红、蓝、黄三类.由于这种描述方法形象直观，因而在竞赛数学中得到广泛的应用. 下面我们主要讨论图的染色、平面染色及网格染色问题. 1．基本原理

为了说话方便，我们作如下约定：若将图G的边用k种颜色染，每条边恰染一种颜色，则把这种染色图称为k染色图.若将图G的顶点用k种颜色染，每个顶点恰染一种颜色，则把这种染色图称为k顶点染色图. 若将平面上的点用k种颜色染，每个点恰染一种颜色，则把这种染色平面称为k染色平面.若将m?n的棋盘的?m?1??n?1?个格点用k种颜色染，每个格点恰染一种颜色，则把这种染色的棋盘称为k染色的网格.需要说明的是，将一组对象用k种颜色染色时，并不要求染色完后每种颜色的对象都要出现. 另外，我们还约定：在对图的边染色之后，边的颜色全相同的r阶完全子图称为同色kr，同色k3又称为同色三角形.

定理1 二染色的k6必有同色三角形. 完全图k5可以二染色使其不含同色三角形. 二染色的k5不含同色三角形的充要条件是k5由2个颜色相异的长为5的同色圈构成.

证

求数列通项公式的方法

一、公式法

例1 已知数列{an}满足an?1?2an?3?2n，a1?2，求数列{an}的通项公式。

an?1an3an?1an3an????{}是，则，故数列n?1nn?1nn2222222an3a23??1?1?(n?1)以1为首项，以为公差的等差数列，由等差数列的通项公式，得，21222n231n所以数列{an}的通项公式为an?(n?)2。

22解：an?1?2an?3?2n两边除以2n?1，得

评注：本题解题的关键是把递推关系式an?1?2an?3?2n转化为

an?1an3?n?，说明数列n?1222aan3{n}?1?(n?1)是等差数列，再直接利用等差数列的通项公式求出，进而求出数列nn222{an}的通项公式。

二、累加法

例2 已知数列{an}满足an?1?an?2n?1，a1?1，求数列{an}的通项公式。 解：由an?1?an?2n?1得an?1?an?2n?1则

an?(an?an?1)?(an?1?an?2)???(a3?a2)?(a2?a1)?a1?[2(n?1)?1]?[2(n?2)?1]???(2?2?1)?(2?1?1)?1?2[(n?1)?(n?2)???2?1]?(n?1)?1(

课题：由递推公式求通项公式

教材分析：由课本的等差、等比通项公式的推导过程，总结出其他递推公式如何求通项公式。 教学目的：

思想教育：培养学生在求解通项问题上掌握在社会上为人处事，解决问题的能力；

知识传授：数列的递推公式向通项公式转化的基本方法； 能力培养：培养学生的逻辑推理能力，分析问题、解决问题的能力，利用课本所学知识举一反三；

情感培养：促进师生间的交流与合作，培养学生与他人的交往能力及团结协作能力。

教学重点：数列的递推公式，通项公式及求通项公式； 教学难点：如何分析递推公式，进而求出通项公式； 教学方法：启发式教学 课 型：拓展延伸课 课 时：1节课 教学步骤：

一、 复习回顾：

师：回忆什么是递推公式？什么是通项公式？ （学生讨论、交流，总结回忆课本上的定义） 师：见教材P113面，看到递推公式定义

1

递推公式：如果已知数列｛an｝的第1项（或前几项）且任一项

an与它的前一项an?1（或前几项）间的关系可以用一个公式来表示，

那么这个公式叫做数列的递推公式。

师：见教材P110面，看到通项公式的定义

通项公式：数学｛an｝的第n项an与n之间的关系可以用一个公式来表示，这个公式就叫做这个数列的通项公式。

课题：由递推公式求通项公式

教材分析：由课本的等差、等比通项公式的推导过程，总结出其他递推公式如何求通项公式。 教学目的：

思想教育：培养学生在求解通项问题上掌握在社会上为人处事，解决问题的能力；

知识传授：数列的递推公式向通项公式转化的基本方法； 能力培养：培养学生的逻辑推理能力，分析问题、解决问题的能力，利用课本所学知识举一反三；

情感培养：促进师生间的交流与合作，培养学生与他人的交往能力及团结协作能力。

教学重点：数列的递推公式，通项公式及求通项公式； 教学难点：如何分析递推公式，进而求出通项公式； 教学方法：启发式教学 课 型：拓展延伸课 课 时：1节课 教学步骤：

一、 复习回顾：

师：回忆什么是递推公式？什么是通项公式？ （学生讨论、交流，总结回忆课本上的定义） 师：见教材P113面，看到递推公式定义

1

递推公式：如果已知数列｛an｝的第1项（或前几项）且任一项

an与它的前一项an?1（或前几项）间的关系可以用一个公式来表示，

那么这个公式叫做数列的递推公式。

师：见教材P110面，看到通项公式的定义

通项公式：数学｛an｝的第n项an与n之间的关系可以用一个公式来表示，这个公式就叫做这个数列的通项公式。

第 1 页 共 1 页

最全的待定系数法求递推数列通项

用待定系数法求递推数列通项公式初探

摘要: 本文通过用待定系数法分析求解9个递推数列的例题，得出适用待定系数法求其通项公式的七种类型的递推数列，用于解决像观察法、公式法、迭乘法、迭加法、裂项相消法和公式法等不能解决的数列的通项问题。 关键词:变形 对应系数 待定 递推数列

数列在高中数学中占有重要的地位，推导通项公式是学习数列必由之路，特别是根据递推公式推导出通项公式，对教师的教学和学生的学习来说都是一大难点，递推公式千奇百怪，推导方法却各不相同，灵活多变。对学生的观察、分析能力要求较高，解题的关键在于如何变形。常见的方法有观察法、公式法、迭乘法、迭加法、裂项相消法和公式法。但是对比较复杂的递推公式，用上述方法难以完成，用待定系数法将递推公式进行变

递推数列通项求解方法

类型一：an?1?pan?q（p?1）

思路1（递推法）：an?pan?1?q?p(pan?2?q)?q?p??p?pan?3?q??q???q? ……?pn?1a1?q(1?p?p2?…?pn?2?q?qn?1。 )??a1??p??p?11?p??思路2（构造法）：设an?1???p?an???，即??p?1??q得??qp?1，数列

?an???是以a1??为首项、p为公比的等比数列，则an??q?n?1qan??a1?p?。 ?p?11?p???q?n?1??a1??p，即p?1?p?1?q例1 已知数列?an?满足an?2an?1?3且a1?1，求数列?an?的通项公式。 解：方法1（递推法）：

an?2an?1?3?2(2an?2?3)?3?2??2?2an?3?3??3???3?……?2n?1?3(1?2?2?…?22n?23?n?13?n?1)??1??2??2?3。 ?2?1?1?2?方法2（构造法）：设an?1???2?an???，即??3，?数列?an?3?是以a1?3?4n?1n?1n?1为首项、2为公比的等比数列，则an?3?4?2?2，即an?2?3。

1

类型二：an?1?an?思路1（递推

递推数列通项求解方法

类型一：an?1?pan?q（p?1）

思路1（递推法）：an?pan?1?q?p(pan?2?q)?q?p??p?pan?3?q??q???q? ……?pn?1a1?q(1?p?p2?…?pn?2?q?qn?1。 )??a1??p??p?1?1?p?思路2（构造法）：设an?1???p?an???，即??p?1??q得??qp?1，数列

?an???是以a1??为首项、p为公比的等比数列，则an??q?n?1qan??a1?p?。 ?p?11?p???q?n?1??a1??p，即p?1?p?1?q例1 已知数列?an?满足an?2an?1?3且a1?1，求数列?an?的通项公式。 解：方法1（递推法）：

an?2an?1?3?2(2an?2?3)?3?2??2?2an?3?3??3???3?……?2n?1?3(1?2?2?…?22n?23?n?13?n?1)??1??2??2?3。 ?2?1?1?2?方法2（构造法）：设an?1???2?an???，即??3，?数列?an?3?是以a1?3?4n?1n?1n?1为首项、2为公比的等比数列，则an?3?4?2?2，即an?2?3。

类型二：an?1?an?思路1（递推法）