Pour résoudre la relation de récurrence 
𝑇
(
𝑛
)
=
𝑇
(
𝑛
−
2
)
+
1
T(n)=T(n−2)+1, nous allons suivre une méthode rigoureuse.

Diagnostic

Cette relation de récurrence est linéaire, non homogène, d'ordre 2. Elle décrit une suite où chaque terme dépend du terme deux positions avant lui, avec un ajout constant de 1.

Résolution

a) Résolution de l'équation homogène associée
L'équation homogène associée est :

𝑇
ℎ
(
𝑛
)
=
𝑇
ℎ
(
𝑛
−
2
)
T
h
	​

(n)=T
h
	​

(n−2)

L'équation caractéristique est :

𝑟
2
=
1
r
2
=1

Les racines sont 
𝑟
=
1
r=1 et 
𝑟
=
−
1
r=−1.

La solution générale de l'équation homogène est donc :

𝑇
ℎ
(
𝑛
)
=
𝐴
⋅
(
1
)
𝑛
+
𝐵
⋅
(
−
1
)
𝑛
=
𝐴
+
𝐵
(
−
1
)
𝑛
T
h
	​

(n)=A⋅(1)
n
+B⋅(−1)
n
=A+B(−1)
n

b) Recherche d'une solution particulière
La non-homogénéité est une constante 
+
1
+1. Nous cherchons une solution particulière constante 
𝑇
𝑝
(
𝑛
)
=
𝐶
T
p
	​

(n)=C.

En substituant dans l'équation de récurrence :

𝐶
=
𝐶
+
1
C=C+1

Cela conduit à une contradiction, ce qui signifie qu'il faut essayer une solution particulière de la forme 
𝑇
𝑝
(
𝑛
)
=
𝐷
𝑛
T
p
	​

(n)=Dn.

Substituons 
𝑇
𝑝
(
𝑛
)
=
𝐷
𝑛
T
p
	​

(n)=Dn dans l'équation :

𝐷
𝑛
=
𝐷
(
𝑛
−
2
)
+
1
Dn=D(n−2)+1


𝐷
𝑛
=
𝐷
𝑛
−
2
𝐷
+
1
Dn=Dn−2D+1


0
=
−
2
𝐷
+
1
0=−2D+1


𝐷
=
1
2
D=
2
1
	​


La solution particulière est donc :

𝑇
𝑝
(
𝑛
)
=
1
2
𝑛
T
p
	​

(n)=
2
1
	​

n

c) Solution générale
La solution générale est la somme de la solution homogène et de la solution particulière :

𝑇
(
𝑛
)
=
𝐴
+
𝐵
(
−
1
)
𝑛
+
1
2
𝑛
T(n)=A+B(−1)
n
+
2
1
	​

n

Détermination des constantes 
𝐴
A et 
𝐵
B

Pour déterminer 
𝐴
A et 
𝐵
B, il faut des conditions initiales. Supposons que :

𝑇
(
0
)
=
𝑐
0
T(0)=c
0
	​



𝑇
(
1
)
=
𝑐
1
T(1)=c
1
	​


En substituant 
𝑛
=
0
n=0 :

𝑇
(
0
)
=
𝐴
+
𝐵
(
−
1
)
0
+
1
2
⋅
0
=
𝐴
+
𝐵
=
𝑐
0
T(0)=A+B(−1)
0
+
2
1
	​

⋅0=A+B=c
0
	​


En substituant 
𝑛
=
1
n=1 :

𝑇
(
1
)
=
𝐴
+
𝐵
(
−
1
)
1
+
1
2
⋅
1
=
𝐴
−
𝐵
+
1
2
=
𝑐
1
T(1)=A+B(−1)
1
+
2
1
	​

⋅1=A−B+
2
1
	​

=c
1
	​


Nous avons donc le système :
\[
\begin{cases}
A + B = c_0 \\
A - B = c_1 - \frac{1}{2}
\end{cases}
\]

La résolution donne :
\[
A = \frac{c_0 + c_1 - \frac{1}{2}}{2}, \quad B = \frac{c_0 - c_1 + \frac{1}{2}}{2}
\]

Solution finale

La solution générale de la récurrence est :
\[
T(n) = \frac{c_0 + c_1 - \frac{1}{2}}{2} + \frac{c_0 - c_1 + \frac{1}{2}}{2} (-1)^n + \frac{1}{2}n
\]

Exemple avec des conditions initiales

Supposons 
𝑇
(
0
)
=
0
T(0)=0 et 
𝑇
(
1
)
=
0
T(1)=0. Alors :
\[
A = \frac{0 + 0 - \frac{1}{2}}{2} = -\frac{1}{4}, \quad B = \frac{0 - 0 + \frac{1}{2}}{2} = \frac{1}{4}
\]

La solution devient :
\[
T(n) = -\frac{1}{4} + \frac{1}{4}(-1)^n + \frac{1}{2}n
\]

Vérification

Pour 
𝑛
=
0
n=0 :

𝑇
(
0
)
=
−
1
4
+
1
4
+
0
=
0
T(0)=−
4
1
	​

+
4
1
	​

+0=0

Pour 
𝑛
=
1
n=1 :

𝑇
(
1
)
=
−
1
4
−
1
4
+
1
2
=
0
T(1)=−
4
1
	​

−
4
1
	​

+
2
1
	​

=0

Pour 
𝑛
=
2
n=2 :

𝑇
(
2
)
=
−
1
4
+
1
4
+
1
=
1
T(2)=−
4
1
	​

+
4
1
	​

+1=1

Cela correspond bien à 
𝑇
(
2
)
=
𝑇
(
0
)
+
1
=
1
T(2)=T(0)+1=1.

Conclusion

La solution générale de la récurrence 
𝑇
(
𝑛
)
=
𝑇
(
𝑛
−
2
)
+
1
T(n)=T(n−2)+1 est :
\[
T(n) = A + B(-1)^n + \frac{1}{2}n
\]
où 
𝐴
A et 
𝐵
B sont déterminés par les conditions initiales.