Given PRNG $G(s)$, why is $G(s) || G(s+1)$ not a PRNG? I have given a pseudorandom Generator $G(s)$, $|s|=n$ whose expansion $l(n)$ is $&gt;2n$. I also know that $G^\prime(s) := G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor})$ is a pseudorandom generator. Now the function 

$\begin{equation}L(s) := G(s) ~||~ G(s+1)\end{equation}$

with $||$ being concatenation is supposed to be no pseudorandom generator and I struggle to prove it. Intuitively, I would think that since $L$ passes two different seeds to $G$ and $G$ is pseudorandom, $L$ must be pseudorandom too. $G(s+1)$ should be unpredictably different from $G(s+1)$ for a PRNG, should it not? Could someone point me into the right direction?
$L$ is not necessarily a pseudorandom generator, but it may be. Hence, there is no hope of proving that $L$ is not a pseudorandom generator from what you are given. Rather, you must exhibit a pseudorandom generator $G$ such that $L$ is not a pseudorandom generator. Here is the canonical example with expansion factor $n+1$.

Let $f$ be a one-way permutation (i.e., an injective, length-preserving one-way function). Then it is known that the following is a pseudorandom generator with expansion factor $n+1$:


  
  Choose uniformly a seed $s$ of even length $s_1s_2\dots s_{2n}$.
  Compute $b = \sum_{i=1}^n s_is_{n+i}$ (with arithmetic in $\mathbf{F}_2$).
  Output $f(s_1s_2\dots s_n)s_{n+1}s_{n+2}\dots s_{2n}b$.
  


Now, if $s$ is uniformly chosen, with probability $1/2$ its last bit will be $0$, meaning that $s+1$ will be just $s$ with the last bit ($s_{2n}$) flipped, and in turn it means that $G(s+1)$ will equal $G(s)$ except possibly in the last two bits. Hence, a distinguisher can check whether the second half of its input string equals the first one disregarding the last two bits of each. If the string is $G(s)G(s+1)$, this happens with probability at least $1/2$, whereas if the string is truly random this happens with probability $1/2^{n-2}$.