Checking linearity/time-invariance etc. for recursive system I'm familiar with the general methodology for checking if a system is linear:


Define output $y_1[n]$ for input $x_1[n]$, define output $y_2[n]$ for input $x_2[n]$
Define $x_3[n] = ax_1[n] + bx_2[n]$
Compute output $y_3[n]$ for input $x_3[n]$ and verify whether $y_3[n]=ay_1[n]+by_2[n]$. If it is, the system is linear.


However, I am having trouble applying this method to systems that are recursive. Some recursive systems can be converted to an iterative form by inspection. For example:
$y[n] - y[n-1] = x[n] \implies y[n] = x[n] + y[n-1] \implies y[n] = \sum\limits_{k=-\infty}^n x[k]$

For others, I am having more trouble, such as $y[n]+y[n+1]=x[n]$

First, I do a change of variables:

$k = n+1 \implies y[k]+y[k-1]=x[k-1]$

Following the general approach: 

$y_1[k]+y_1[k-1] = x_1[k-1]$

$y_2[k]+y_2[k-1] = x_2[k-1]$

$x_3[k] = ax_1[k]+bx_2[k]$

$y_3[k]+y_3[k-1] = x_3[k-1] = ax_1[k-1]+bx_2[k-1]$

Here is where I got stuck. I was anticipating that the system should be linear, but due to the recursive term, I do not see how the approach I took could yield $y_3[n] = ay_1[n]+by_2[n]$.

Does anyone know where I made a mistake, or if there is a different approach I should be taking? (For instance, is there a general process for going from a recursive expression to an iterative one that I could use?) I'm a student using Oppenheim and Schafer for reference.
You made no mistake. Following the hint in Dilip Sarwate's comment, you will be able to show the following input-output relation of the system:

$$y[n]=x[n-1]-x[n-2]+x[n-3]-+\ldots=\sum_{k=-\infty}^{n-1}(-1)^{n-k-1}x[k]\tag{1}$$

Using this relation, showing linearity will be much easier.

Furthermore, note that any system described by a linear difference equation with constant coefficients is linear and time-invariant (if the initial conditions are zero!). And your system obviously belongs to this class.